四数之和【LC18】
给你一个由
n个整数组成的数组nums，和一个目标值target。请你找出并返回满足下述全部条件且不重复的四元组[nums[a], nums[b], nums[c], nums[d]]（若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < na、b、c和d互不相同nums[a] + nums[b] + nums[c] + nums[d] == target你可以按 任意顺序 返回答案 。
排序+双指针
- 思路
- 注意去重以及溢出
- 优化：
- 判断最小四元组是否大于target，是则break
- 判断最大四元组是否小于target，实则continue
- 实现
class Solution { public List<List<Integer>> fourSum(int[] nums, int target) { List<List<Integer>> res = new ArrayList<>(); int n = nums.length; Arrays.sort(nums); for (int i = 0; i < n - 3; i++){ if (i > 0 && nums[i] == nums[i - 1]) continue; long x = nums[i]; if (x + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break; if (x + nums[n - 1] + nums[n - 2] + nums[n - 3] < target) continue; for (int j = i + 1; j < n - 2; j++){ if (j > i + 1 && nums[j] == nums[j - 1]) continue; long sum2 = nums[i] + nums[j]; int l = j + 1, r = n - 1; long num = target - sum2; while (l < r){ if (nums[l] + nums[r] == num){ res.add(Arrays.asList(nums[i], nums[j], nums[l], nums[r])); l++; while (l < n && nums[l - 1] == nums[l]){ l++; } r--; while (r > l && nums[r + 1] == nums[r]){ r--; } }else if (nums[l] + nums[r] > num){ r--; }else{ l++; } } } } return res; } }
