欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

给一个升序数组,找出两个数字相加等于 target 的个数。

程序员文章站 2024-02-04 08:18:10
...
int[] nums = {1,2,2,3,3,3,3,4,4,5,5}   target = 6  res = 12

public int twoSum(int[] nums, int target) {
        int n = nums.length;
        if (n <= 0) return 0;
        int count = 0;
        for (int lo = 0, hi = n-1; lo < hi;) {
            if      (nums[lo] + nums[hi] < target) lo++;
            else if (nums[lo] + nums[hi] > target) hi--;
            else {
                if (nums[lo] != nums[hi]) {
                    int count1 = 0;
                    int tmp1 = nums[lo];
                    while (nums[lo] == tmp1) {
                        count1++;
                        lo++;
                    }

                    int count2 = 0;
                    int tmp2 = nums[hi];
                    while (nums[hi] == tmp2) {
                        count2++;
                        hi--;
                    }

                    count += count1 * count2;

                } else {
                    int count1 = 0;
                    int tmp = nums[lo];
                    while (nums[lo] == tmp) {
                        count1++;
                        lo++;
                    }

                    count += count1 * (count1 - 1) / 2;   // count1 取两个  C n 2
                }

            }
        }
        return count;
    }
    
如果数组是无序的

public int twoSum(int[] nums, int target) {
        int n = nums.length;
        if (n <= 0) return 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        int count = 0;
        for (int i = 0; i < n; i++) {

            if (map.containsKey(target-nums[i])) {
                count += map.get(target - nums[i]);
            }

            if (map.containsKey(nums[i])) {
                map.put(nums[i], map.get(nums[i]) + 1);
            }
            else {
                map.put(nums[i], 1);
            }
        }
        return count;
    }

相关标签: 字节