https://leetcode.cn/problems/4sum/
题面
题意:给定一个包含 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] ]
思路 双指针 ,时间O(n^3)
有个已经踩过坑的细节需要注意! 不要判断nums[k] > target
就返回了,三数之和 可以通过 nums[i] > 0
就返回了,因为 0 已经是确定的数了,四数之和这道题目 target是任意值。比如:数组是[-4, -3, -2, -1]
,target
是-10
,不能因为-4 > -10
而跳过。
思路和三数之和没太大区别,都是双指针,在三数之和的基础上再套一层for。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43
| public List<List<Integer>> fourSum(int[] nums, int target) { List<List<Integer>> result = new ArrayList<>(); Arrays.sort(nums); for (int i = 0; i < nums.length; i++) { if (nums[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++) { if (nums[j] > 0 && nums[i] + nums[j] > target) return result; if (j > i + 1 && nums[j] == nums[j - 1]) continue; int left = j + 1; int right = nums.length - 1; while (right > left) { long sum = (long) 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 (right > left && nums[right] == nums[right - 1]) right--; while (right > left && nums[left] == nums[left + 1]) left++; right--; left++; } } } } return result; }
|