NSUM 问题

两数之和

问题描述
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例1

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0]   nums[1] = 2   7 = 9
所以返回 [0, 1]

示例2

输入：numbers = [2,3,4], target = 6
输出：[1,3]
解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。

示例3

输入：numbers = [-1,0], target = -1
输出：[1,2]
解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

代码

static int[] twoSum(int[] nums, int target) {
    int l = 0;
    int r = nums.length - 1;
    while (l < r) {
    	//整体数字偏小，l右移
        if (nums[l]   nums[r] < target) {
            l  ;
            //整体数字偏大，r左移
        } else if (nums[l]   nums[r] > target) {
            r--;
        } else {
            return new int[]{l, r};
        }
    }
    return null;
}

两数之和 2（多个结果集去重）

问题描述
nums 中可能有多对儿元素之和都等于 target，请你的算法返回所有和为 target 的元素对儿，其中不能出现重复。
示例

nums = [1,3,1,2,2,3], target = 4
结果：[[1,3],[2,2]]

思路
出问题的地方在于 sum == target 条件的 if 分支，当给 res 加入一次结果后，l 指针和 h 指针不应该直接修改，还应该跳过所有重复的元素。

代码1：指针偏移的时候校验

static List<List<Integer>> twoSum(int[] nums, int target) {
    List<List<Integer>> result = new ArrayList<>();

    Arrays.sort(nums);

    int l = 0;
    int r = nums.length - 1;
    while (l < r) {
        int numL = nums[l];
        int numR = nums[r];

        //整体数字偏小，l右移
        if (numL   numR < target) {
            while (l < r && nums[l] == numL) {
                l  ;
            }
            //整体数字偏大，r左移
        } else if (numL   numR > target) {
            while (l < r && nums[r] == numR) {
                r--;
            }
        } else {
            result.add(Arrays.asList(numL, numR));
            //l指针跳过与当前值相同的下标
            while (l < r && nums[l] == numL) {
                l  ;
            }
            //r指针跳过与当前值相同的下标
            while (l < r && nums[r] == numR) {
                r--;
            }
        }
    }
    return result;
}

代码2：返回值用set去重

static Set<List<Integer>> twoSum(int[] nums, int target) {
    Set<List<Integer>> result = new HashSet<>();

    Arrays.sort(nums);

    int l = 0;
    int r = nums.length - 1;
    while (l < r) {
        int numL = nums[l];
        int numR = nums[r];

        //整体数字偏小，l右移
        if (numL   numR < target) {
            l  ;
            //整体数字偏大，r左移
        } else if (numL   numR > target) {
            r--;
        } else {
            result.add(Arrays.asList(numL, numR));
            l  ;
            r--;
        }
    }
    return result;
}

15. 三数之和

问题描述
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 *a，b，c ，*使得 a b c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

代码

static Set<List<Integer>> threeSum(int[] arr) {
    //set可以自动去重结果集
    Set<List<Integer>> result = new HashSet<>();
    //数据排序
    Arrays.sort(arr);
    //以arr[i]为基准数，利用左右指针遍历其他两个值
    for (int i = 0; i < arr.length; i  ) {
        int l = i   1;
        int r = arr.length - 1;

        while (l < r) {
            //如果三个数之和小于0，则左指针右移，整体增大
            if (arr[i]   arr[l]   arr[r] < 0) {
                l  ;
                //如果三个数之和大于0，则右指针左移，整体减少
            } else if (arr[i]   arr[l]   arr[r] > 0) {
                r--;
            } else {
                //如果三个数之和等于0，则右指针左移，左指针右移，继续找下一组数据
                result.add(Arrays.asList(arr[i], arr[l], arr[r]));
                l  ;
                r--;
            }
        }
    }
    return result;
}

来源：https://mp.weixin.qq.com/s/fSyJVvggxHq28a0SdmZm6Q

这篇好文章是转载于：学新通技术网