题目
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：答案中不可以包含重复的四元组。
示例：
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。 满足要求的四元组集合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]
分析
大致的解题思路就是，前后两个指针同时走，获取到的值减去target的值，再次基础上继续向前或者向后移到以为，获取到的值与上一步骤中的值相加为0，则此时的四个值是符合要求的。
解答
public class Solution { public List<List<Integer>> fourSum(int[] num, int target) { List<List<Integer>> rst = new ArrayList<List<Integer>>(); Arrays.sort(num); for (int i = 0; i < num.length - 3; i++) { if (i != 0 && num[i] == num[i - 1]) { continue; } for (int j = i + 1; j < num.length - 2; j++) { if (j != i + 1 && num[j] == num[j - 1]) continue; int left = j + 1; int right = num.length - 1; while (left < right) { int sum = num[i] + num[j] + num[left] + num[right]; if (sum < target) { left++; } else if (sum > target) { right--; } else { ArrayList<Integer> tmp = new ArrayList<Integer>(); tmp.add(num[i]); tmp.add(num[j]); tmp.add(num[left]); tmp.add(num[right]); rst.add(tmp); left++; right--; while (left < right && num[left] == num[left - 1]) { left++; } while (left < right && num[right] == num[right + 1]) { right--; } } } } } return rst; } }
