双指针解决NSum问题

1.两数之和

public int[] twoSum(int[] nums, int target) {
        /**
         *  首先，对于该题要求返回原始数组下标，这里就要求不能手动排序
         *  所以二分的思路行不通，
         *  但是这里可以使用哈希表，降低时间复杂度。使用哈希表时，由于哈希表刚开始并没有创建啊
         *
         */
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int need = target - nums[i];
            if (map.containsKey(need)){
                return new int[]{i, map.get(need)};
            }
            map.put(nums[i], i);
        }
        return null;
    }

此时表不能进行排序。因为人家要求返回原始数组下标。
这里刚开始遍历时，哈希表里并没有数据，但是如果前面某个数事最后要返回的那个数字，在后面遍历的时候一定会和前面的数据配对，也就是说哈希表里这时候有数据了。

2.三数之和

[-1,0,1,2,-1,-4]
排序之后是：
[-4, -1, -1, 0, 1, 2]
分析：依次选取第一个第二个数，

1. 对于第一个数来说，不能选取重复的，因为选取了第一个数为-1，第二次再以-1作为第一个数的话，第二个数得到的结果一定是第一个-1得到的结果的子集。
2. 对于第2个数来说，第二个数也不能相同，这样得到的一定是相同的结果集。

class Solution {
public List<List> threeSum(int[] nums) {
//首先是排序为有序数组
Arrays.sort(nums);
int n = nums.length;
//存放最终结果
List<List> ans = new ArrayList<>();

    for (int i = 0; i < n; i++) {
        //对于选取的第一个数字
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }
        //每一轮开始的条件：
        int j = i + 1;
        int k = n - 1;
        while (j < k) {
            //能够提前判断并且结束
            while (j > i + 1 && j < n && nums[j] == nums[j - 1]){
                j++;
            }
            if (j >= k) {
                break;
            }

            int sum = nums[i] + nums[j] + nums[k];
            if (sum == 0){
                //注意添加结果集的操作，添加之后，还是要判断更新j的值
                ans.add(Arrays.asList(nums[i], nums[j], nums[k]));
                j++;
            }else if (sum > 0){
                k--;
            }else if (sum < 0){
                j++;
            }
        }
    }
    return ans;
}

}

3. 最接近的三数之和

public int threeSumClosest(int[] nums, int target) {
        /**
         * 为了找到最接近target的三数之和，必须要使用取绝对值函数，但是这里要谨记，
         * 对于初始值应该让其初始化为数组中的元素之和，不能随意的初始化。
         */
        Arrays.sort(nums);
        int n = nums.length;
        int res = nums[0] + nums[1] + nums[2];

        for (int i = 0; i < n; i++) {
            if (i > 0 && nums[i] == nums[i - 1]){
                continue;
            }
            int j = i + 1;
            int k = n - 1;
            while (j < k){
                if (j > i + 1 && j < n && nums[j] == nums[j - 1]){
                    j++;
                }
                if (j >= k){
                    break;
                }
                int sum = nums[i] + nums[j] + nums[k];
//              res = Math.min(Math.abs(target - sum), res);
                res = Math.abs(sum - target) < Math.abs(res -target) ? sum : res;
//                if(Math.abs(sum - target) < Math.abs(res - target)){
//                    res = sum;
//                }
                if (sum == target){
                    return sum;
                }else if (sum > target){
                    k--;
                }else if (sum < target){
                    j++;
                }
            }
        }
        return res;
    }

18.四数之和

public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        int n = nums.length;

        for (int i = 0; i < n; i++) {
            //控制第一个数
            if (i > 0 && nums[i] == nums[i - 1]){
                continue;
            }
            //控制第二个数
            for (int j = i + 1; j < n; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]){
                    continue;
                }

                int k = j + 1;
                int p = n - 1;
                while (k < p){
                    while (k > j + 1 && k < n && nums[k] == nums[k - 1]){
                        k++;
                    }
                    while (k >= n){
                        break;
                    }
                    //这里是因为leecode给出的测试案例太大，溢出，最好转为long类型
                    long sum = (long) nums[i] + nums[j] + nums[k] + nums[p];
                    if (sum == target){
                        res.add(Arrays.asList(nums[i], nums[j], nums[k], nums[p]));
                        k++;
                    }
                    else if (sum > target){
                        p--;
                    } else if (sum < target) {
                        k++;
                    }
                }
            }
        }
        return res;
    }

这样对于NSum问题来说就有一个很好的解决方法：
直接使用3Sum作为迭代终点，其他的依次调用(n-1)Sum即可