LeetCode18.四数之和

题目链接：18. 四数之和 - 力扣（LeetCode）

这道题是在三数之和上改编出来的，在写这道题之前可以尝试以下三数之和（15. 三数之和 - 力扣（LeetCode））；

1.常规解法（会超时）

由于这道题的结果不能出现含相同元素的三元组，则可以先对目标数组排，以防出现结果中元素相同但顺序不同的情况；

接下可以遍历这个数组，先找到所有的三元组，再挑选出符合条件的三元组，代码如下：

    public List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>> ret = new ArrayList<>();int n = nums.length;Arrays.sort(nums);for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {for (int k = j + 1; k < n; k++) {for (int l = k + 1; l < n; l++) {if ((long)nums[i] + (long)nums[j] + (long)nums[k] + (long)nums[l] == (long)target) {List<Integer> list = new ArrayList<>();list.add(nums[i]);list.add(nums[j]);list.add(nums[k]);list.add(nums[l]);if (!ret.contains(list)) {ret.add(list);}}}}}}return ret;}

注意：我们再进行判断时，涉及到四个数据相加，由于整形数据的最大值是2147483647,会出现1000000000 + 1000000000 + 1000000000  +1000000000 = -294967296的情况，这与实际情况不符，这时就需要类型转换，由于long类型的数据范围更大，就可以将int转化为long再相加比较。

2.双指针算法

和三数之和一样，我么可以先固定最后一个数，在前面的数中找到和为（target - 最后一个数）；

因为有去重操作，可以先对数组从小到大排序；

先定义四个指针p1，p2，left，right，p1指向最后一个数，p2指向倒数第二个数，left指向第一个数，right指向p2前一个数；

现保持p1和p2不动，让left与right相向运动，若(long)nums[left] + (long)nums[right] + (long)nums[p1] + (long)nums[p2] == target，则将这个四元组添加到结果中，由于不能出现出重复的四元组，就需要去除与left和right指向元素相同的元素；若(long)nums[left] + (long)nums[right] + (long)nums[p1] + (long)nums[p2] < target，由单调性知，以left为基准，right左边的数均小于right指向的元素，相加之后结果必小于target，就需要将left向右移动一位；若(long)nums[left] + (long)nums[right] + (long)nums[p1] + (long)nums[p2] > target，由单调性知，以right为基准，left右边的元素均大于left指向的元素，相加之后结果必大于target，就需要将right左移一位；

当left与right相遇后，内层的一轮循环就结束了，就需要将p2向左移动一位，同样的，也需要进行去重操作，除去与p2指向元素相同的元素；

当p2==1时，p2已经走完一遍，就需要向左移动p1继续下一轮循环，同样的，也需要进行去重操作，去除与p1指向元素相同的元素，流程图与代码如下：

    public List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>> ret = new ArrayList<>();Arrays.sort(nums);int n = nums.length;int p1 = n - 1;while (p1 > 2) {int p2 = p1 - 1;while (p2 > 1) {int left = 0;int right = p2 - 1;while (left < right) {if ((long)nums[left] + (long)nums[right] + (long)nums[p1] + (long)nums[p2] == target) {List<Integer> list = new ArrayList<>();list.add(nums[left]);list.add(nums[right]);list.add(nums[p1]);list.add(nums[p2]);ret.add(list);int numLeft = nums[left++];while (nums[left] == numLeft && left < right) {left++;}int numRight = nums[right++];while (nums[right] == numRight && left < right) {right--;}} else if ((long)nums[left] + (long)nums[right] + (long)nums[p1] + (long)nums[p2] < target) {left++;} else {right--;}}int numP2 = nums[p2--];while (nums[p2] == numP2 && p2 > 1) {p2--;}}int numP1 = nums[p1--];while (nums[p1] == numP1 && p1 > 2) {p1--;}}return ret;}

希望读者指出不足之处！