LeetCode-18四数之和

题目来源

18. 四数之和 - 力扣（LeetCode）

题目描述

给你一个由 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

你可以按 任意顺序 返回答案 。

示例

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：

输入：nums = [2,2,2,2,2], target = 8 输出：[[2,2,2,2]]

提示 1 <= nums.length <= 200-10^9 <= nums[i] <= 10^9-10^9 <= target <= 10^9

题目解析

本题是 LeetCode - 15 三数之和-CSDN博客 的进阶版，解题思路一致。

三数之和、四数之和初始时都是需要将数组升序，方便后续双指针。

三数之和：固定三元组中一个最小值索引 i 然后定义双指针 L = i+1，R = len(nums) - 1，如果此时三元组之和 sum = nums[i] + nums[L] + nums[R]

sum > target，则 R -= 1，因为数组已经升序，因此 R 指针左移，则 nums[R] 变小，对应的三数之和也会变小sum < target，则 L += 1，因为数组已经升序，因此 L 指针右移，则 nums[L] 变大，对应的三数之和也会变大sum == target，则此时 (nums[i], nums[L], nums[R]) 和为 tagret 的三元组。

四数之和：固定四元组中最小两个值的索引 i，j，然后定义双指针 L = j + 1，R = len(nums) - 1，如果此时四元组之和 sum = nums[i] + nums[j] + nums[L] + nums[R]

sum > target，则 R -= 1，因为数组已经升序，因此 R 指针左移，则 nums[R] 变小，对应的四数之和也会变小sum < target，则 L += 1，因为数组已经升序，因此 L 指针右移，则 nums[L] 变大，对应的四数之和也会变大sum == target，则此时 (nums[i], nums[j], nums[L], nums[R]) 和为 tagret 的四元组。

使用双指针的好处是，避免了暴力枚举四元组的四个元素，而是只需要暴力枚举 四元组的最小两个元素，剩余的四元组中较大两个元素可以通过同向双指针优化求解。

之后就是 三元组/四元组 去重问题，这里不推荐得到所有和为 target 的四元组，然后进行去重，而是在求解四元组的过程中就可以去重。这里去重分为两类：

基于 i，j 去重基于 L，R 去重

基于 i，j 去重

比如 nums = [1,1,1,2,3,4]，target=10

如上图所示，红色框部分，其中 i  的位置相同，L，R运动过程也相同，只是 j 的位置发生了变化，但是 j 指向的元素值是没有改变的。

因此当 nums[j] == nums[j - 1] 时，我们可以跳过，比如上图 i = 0，j = 2 的过程可以跳过，因为产生的必然是重复的四元组。

如上图所示，红色框部分，其中 j 的位置相同，L，R的运动过程也相同，只是 i 的位置发生了变化，但是 i 指向的元素值时没有改变的。

因此当 nums[i] == nums[i-1] 时，我们可以跳过，比如上图 i = 1，j=2 的过程可以跳过，因为产生的必然时重复的四元组。

经过上面去重操作，最终只需要进行下面绿色框步骤：

基于 L，R 去重

比如用例 nums = [1,2,3,3,3,4,4,4]，target=10

如下图，绿色框发现了一个target=10的四元组，那么下一步，我们可以：

L += 1，L 右移后，若 nums[L] == nums[L-1]，则此时 i，j，R 未发生变化，则必然和之前四元组重复，我们可以继续 L += 1R -= 1，R 左移后，若 nums[R] == nums[R+1]，则此时 i，j，L 未发生变化，则必然和之前四元组重复，我们可以继续 R -= 1

C源码实现 #include <stdio.h> #include <stdlib.h> /** * Return an array of arrays of size *returnSize. * The sizes of the arrays are returned as *returnColumnSizes array. * Note: Both returned array and *columnSizes array must be malloced, assume * caller calls free(). */ int cmp(const void *a, const void *b) { return *((int *) a) - *((int *) b); } int **fourSum(int *nums, int numsSize, int target, int *returnSize, int **returnColumnSizes) { qsort(nums, numsSize, sizeof(nums[0]), cmp); int **result = (int **) malloc(sizeof(int *) * 1000); int result_size = 0; for (int i = 0; i < numsSize - 3; i++) { if (i > 0 && nums[i] == nums[i - 1]) continue; for (int j = i + 1; j < numsSize - 2; j++) { if (j > i + 1 && nums[j] == nums[j - 1]) continue; int l = j + 1; int r = numsSize - 1; while (l < r) { long sum = (long) nums[i] + nums[j] + nums[l] + nums[r]; if (sum > target) { r--; } else if (sum < target) { l++; } else { int *tuple = (int *) malloc(sizeof(int) * 4); tuple[0] = nums[i]; tuple[1] = nums[j]; tuple[2] = nums[l]; tuple[3] = nums[r]; result[result_size++] = tuple; do { l++; } while (l < r && nums[l] == nums[l - 1]); do { r--; } while (r > l && nums[r] == nums[r + 1]); } } } } *returnSize = result_size; *returnColumnSizes = (int *) malloc(sizeof(int) * result_size); for (int i = 0; i < result_size; i++) { (*returnColumnSizes)[i] = 4; } return result; } //int main() { // int nums[] = {1, 0, -1, 0, -2, 2}; // int numsSize = 6; // int target = 0; // // int returnSize = 0; // int *returnColumnSizes = (int *) calloc(1000, sizeof(int)); // // int **results = fourSum(nums, numsSize, target, &returnSize, &returnColumnSizes); // // for (int i = 0; i < returnSize; i++) { // printf("["); // for (int j = 0; j < returnColumnSizes[i]; j++) { // printf("%d", results[i][j]); // if (j < returnColumnSizes[i] - 1) printf(","); // } // printf("]\n"); // } // // return 0; //}

C++源码实现 class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { sort(nums.begin(), nums.end()); vector<vector<int>> results; int n = nums.size(); for (int i = 0; i < n - 3; i++) { if (i > 0 && nums[i] == nums[i - 1]) continue; for (int j = i + 1; j < n - 2; j++) { if (j > i + 1 && nums[j] == nums[j - 1]) continue; int l = j + 1; int r = n - 1; while (l < r) { long sum = (long)nums[i] + nums[j] + nums[l] + nums[r]; if (sum > target) { r--; } else if (sum < target) { l++; } else { results.emplace_back( vector<int>{nums[i], nums[j], nums[l], nums[r]}); do { l++; } while (l < r && nums[l] == nums[l - 1]); do { r--; } while (r > l && nums[r] == nums[r + 1]); } } } } return results; } };

Java源码实现 class Solution { public List<List<Integer>> fourSum(int[] nums, int target) { Arrays.sort(nums); List<List<Integer>> results = new ArrayList<>(); for (int i = 0; i < nums.length - 3; i++) { if (i > 0 && nums[i] == nums[i - 1]) continue; for (int j = i + 1; j < nums.length - 2; j++) { if (j > i + 1 && nums[j] == nums[j - 1]) continue; int l = j + 1; int r = nums.length - 1; while (l < r) { long sum = (long) nums[i] + nums[j] + nums[l] + nums[r]; if (sum > target) { r--; } else if (sum < target) { l++; } else { ArrayList<Integer> tuple = new ArrayList<>(); tuple.add(nums[i]); tuple.add(nums[j]); tuple.add(nums[l]); tuple.add(nums[r]); results.add(tuple); do { l++; } while (l < r && nums[l] == nums[l - 1]); do { r--; } while (r > l && nums[r] == nums[r + 1]); } } } } return results; } }

Python源码实现 class Solution(object): def fourSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[List[int]] """ nums.sort() results = [] n = len(nums) for i in range(n - 3): if i > 0 and nums[i] == nums[i - 1]: continue for j in range(i + 1, n - 2): if j > i + 1 and nums[j] == nums[j - 1]: continue l = j + 1 r = n - 1 while l < r: total = nums[i] + nums[j] + nums[l] + nums[r] if total > target: r -= 1 elif total < target: l += 1 else: results.append((nums[i], nums[j], nums[l], nums[r])) while l + 1 <= r and nums[l] == nums[l + 1]: l += 1 while r - 1 >= l and nums[r] == nums[r - 1]: r -= 1 l += 1 r -= 1 return results

JavaScript源码实现 /** * @param {number[]} nums * @param {number} target * @return {number[][]} */ var fourSum = function (nums, target) { nums.sort((a, b) => a - b); const results = []; for (let i = 0; i < nums.length - 3; i++) { if (i > 0 && nums[i] == nums[i - 1]) continue; for (let j = i + 1; j < nums.length - 2; j++) { if (j > i + 1 && nums[j] == nums[j - 1]) continue; let l = j + 1; let r = nums.length - 1; while (l < r) { const sum = nums[i] + nums[j] + nums[l] + nums[r]; if (sum > target) { r--; } else if (sum < target) { l++; } else { results.push([nums[i], nums[j], nums[l], nums[r]]); do { l++; } while (l < r && nums[l] == nums[l - 1]); do { r--; } while (r > l && nums[r] == nums[r + 1]); } } } } return results; };