模板

如果出现再一个数组中要求求三个数之和等于一个数，或者四个数和等于一个数，那么此时使用hash表会比较繁琐，推荐使用双指针。
失效情况：Map中讲到的两数之和，此时需要返回索引，但是我们此时需要排序之后进行双指针法，所以返回索引会很麻烦，此时就适合使用map的value存储索引。
以下就是模板，可以把0换成任意的数，就可以使用此模板，注意排序问题，和去重问题。

    /**
        * 双指针+排序
        *
        * @param nums
        * @return
        */
    public List<List<Integer>> threeSum(int[] nums) {
        // 先进行排序
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            // 第一个数都已经大于了0
            if (nums[0] > 0) {
                return res;
            }
            // 去重
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int left = i + 1, right = nums.length - 1;
            while (left < right) {
                int sum = nums[left] + nums[i] + nums[right];
                if (sum > 0) {
                    right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    // 再次去重
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    while (left < right && nums[right] == nums[right - 1]) right--;
                    res.add(Arrays.asList(nums[i],nums[left],nums[right]));
                    left++;
                    right--;
                }
            }
        }
        return res;
    }
}

三数之和

以下例题的详细解析传送🔗

/**
         * 双指针法 + 排序
         *
         * @param nums
         * @return
         */
public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    // 先将数组进行排序
    Arrays.sort(nums);
    // 循环遍历数组
    for (int i = 0; i < nums.length; i++) {
        // 排序后如果第一个数大于0，那么一定不可能凑出三元组
        if (nums[i] > 0) {
            return result;
        }
         // 错误去重方法，将会漏掉-1,-1,2 这种情况
        /*
            if (nums[i] == nums[i + 1]) {
                continue;
            }
            */
        // 两个数相等时，直接跳过这次判断，达到去重效果
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }
        int left = i + 1, right = nums.length - 1;
        while (left < right) {
            // 去重复逻辑如果放在这里，0，0，0 的情况，可能直接导致 right<=left 了，从而漏掉了 0,0,0 这种三元组
            /*
                while (right > left && nums[right] == nums[right - 1]) right--;
                while (right > left && nums[left] == nums[left + 1]) left++;
                */
            int sum = nums[i] + nums[left] + nums[right];
            // 大于0即右指针向左移动
            if (sum > 0) {
                right--;
            }
            // 小于0即左指针向右移动
            else if (sum < 0) {
                left++;
            }
            else{
                result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                // 去重，去重应该放在最后，放在最前面会漏掉0,0,0
                while (right > left && nums[right - 1] == nums[right]) right--;
                while (right > left && nums[left + 1] == nums[left]) left++;
                // 再继续判断是否有相加为0的数
                right--;
                left++;
            }
        }
    }
    return result;
}

四数之和

/**
         * 双指针 + 排序
         *
         * @param nums
         * @param target
         * @return
         */
public List<List<Integer>> fourSum(int[] nums, int target) {
    // 先将数组进行排序
    Arrays.sort(nums);
    List<List<Integer>> result = new ArrayList<>();
    for (int i = 0; i < nums.length; i++) {
        // 第一个数都大于target，那就不会有四元组相加等于target，此时不能使用判断，因为target存在负数
        //                if (i > 0 && nums[i] > target) {
        //                    return result;
        //                }
        // 有重复数据，直接跳过，达到去重效果
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }
        for (int j = i + 1; j < nums.length; j++) {
            // 此处不能判断第一个数大于target就返回，因为此时j不是最外层
            //                    if (i > 0 && nums[i] > target) {
            //                        return result;
            //                    }
            // 有重复数据，直接跳过，达到去重效果
            // 注意此时 j > i + 1 ，不是 j > i ，否则漏掉2，2，2，2，2  8
            if (j > i + 1 && nums[j] == nums[j - 1]) {
                continue;
            }
            int left = j + 1, right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[j] + nums[left] + nums[right];
                if (sum > target) {
                    right--;
                } else if (sum < target) {
                    left++;
                } else {
                    result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                    while (left < right && nums[right] == nums[right - 1]) right--;
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    left++;
                    right--;
                }
            }
        }
    }
    return result;
}