文章目录
- 题目介绍
- 解法
题目介绍
解法
思路和 15. 三数之和 一样，排序后，枚举 nums[a] 作为第一个数，枚举 nums[b] 作为第二个数，那么问题变成找到另外两个数，使得这四个数的和等于 target，这可以用双指针解决。
代码如下:
class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {Arrays.sort(nums);List<List<Integer>> ans = new ArrayList<>();int n = nums.length;for (int a = 0; a < n - 3; a++) { // 枚举第一个数if (a > 0 && nums[a] == nums[a - 1]) continue; // 跳过重复数字for (int b = a + 1; b < n - 2; b++) { // 枚举第二个数if (b > a + 1 && nums[b] == nums[b - 1]) continue; // 跳过重复数字int l = b + 1;int r = n - 1;while (l < r) { // 双指针枚举第三个数和第四个数// nums[a]、nums[b]、nums[l] 和 nums[r] 都是 int 类型的值。//当四个 int 值相加时，它们的和可能会超出 int 类型的最大值。因此需要将其中一个值//转换为 long 类型来避免溢出。这里选择了将 nums[a] 转换为 long 类型，然后与其他三个 int 值相加。long s = (long) nums[a] + nums[b] + nums[l] + nums[r]; // 四数之和，使用 long 避免溢出if (s > target) r--;else if (s < target) l++;else { // s == targetans.add(List.of((int) x, (int) y, nums[l], nums[r]));for (l++; l < r && nums[l] == nums[l - 1]; l++) ; // 跳过重复数字for (r--; r > l && nums[r] == nums[r + 1]; r--) ; // 跳过重复数字}}}}return ans;}
}
