四数之和
题目
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：答案中不可以包含重复的四元组。
示例 1：
输入：nums = [1,0,-1,0,-2,2], target = 0 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：
输入：nums = [], target = 0 输出：[]
提示：
0 <= nums.length <= 200 -109 <= nums[i] <= 109 -109 <= target <= 109
题目分析
1. 暴力解题
时间复杂度：O(N * N *N)
空间复杂度：O(1)
直接通过四重循环来计算。
2. 优化思路
时间复杂度：O(N * N * N)
空间复杂度：O(logN)
解题关键：排序 + 双指针。
题目中要求是不能重复的， 我们可以将输入的整个数组先排序来防止重复。
选择双指针的思路是，我们四个数的和其实可以先取出2个数，然后就看作两个数的和来处理，这样就可以灵活的运用双指针的思路了。
双指针过程中的指针移动。a , b, c, d 下标的移动过程中。
- a 下标需要遍历数组，得到 b + c + d 的和等于 target - a，需要通过前一个来判断是否是重复，如果已经存在就跳过。
- b 下标需要遍历数组，得到 c + d 的和等于 target - a - b，需要通过前一个来判断是否是重复，如果已经存在就跳过。
- c, d 双指针的移动过程，首先初始化 c 的指针位置为 b 的位置 + 1； 并且通过前一个数来判断数据是否存在重复，如果已经存在就跳过。
- d 指针的初始指针位置为 nums.length -1 。如果 c + d > target - a - b 那么就需要把 d 指针左移，否者右移 c 指针，因为已经排序了的。
- 如果 c + d == target - a - b ， 表示找到真确的结果，存储到返回的结果集中。
- 如果 c 指针 == d 指针说明已经找了一圈了，就退出本次的循环，然后在回去移动 a 或 b 指针。
解题代码
public class FourSumEqTargetValTest { public static void main(String[] args) { FourSumEqTargetValTest test = new FourSumEqTargetValTest(); List<List<Integer>> list = test.fourSum(new int[]{1,0,-1,0,-2,2}, 0); System.out.println(list); } public List<List<Integer>> fourSum(int[] nums, int target) { // 数组长度 int len = nums.length; // 排序 Arrays.sort(nums); List<List<Integer>> result = new ArrayList<>(); for (int first = 0; first < len; first++) { // 跳过相同的值 if (first > 0 && nums[first] == nums[first - 1]) { continue; } int leftVal = target - nums[first]; for (int second = first + 1; second < len; second++) { // 跳过相同的值 if (second > first + 1 && nums[second] == nums[second - 1]) { continue; } int fourth = len - 1; int lv = leftVal- nums[second]; for (int third = second + 1; third < len; third++) { // 跳过相同的值 if (third > second + 1 && nums[third] == nums[third - 1]) { continue; } // 保证 c 的指针在 d 的左边 while (third < fourth && nums[third] + nums[fourth] > lv) { --fourth; } // 如果指针重合，随后 b 继续增加 // 如果没有满足 a + b + c + d= 0 , 并且 d < c 了, 退出循环 if (third == fourth) { break; } // 找到合适的解，放入结果集合 if (nums[third] + nums[fourth] == lv) { result.add(Arrays.asList(nums[first], nums[second], nums[third], nums[fourth])); } } } } return result; } }
