LeetCode - 18 四數之和

題目來源

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

題目描述

給你一個由?n?個整數組成的數組?nums?，和一個目標值?target?。請你找出并返回滿足下述全部條件且不重復的四元組?[nums[a], nums[b], nums[c], nums[d]]?（若兩個四元組元素一一對應，則認為兩個四元組重復）：

0 <= a, b, c, d?< n
a、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 += 1
R -= 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]:continuefor j in range(i + 1, n - 2):if j > i + 1 and nums[j] == nums[j - 1]:continuel = j + 1r = n - 1while l < r:total = nums[i] + nums[j] + nums[l] + nums[r]if total > target:r -= 1elif total < target:l += 1else:results.append((nums[i], nums[j], nums[l], nums[r]))while l + 1 <= r and nums[l] == nums[l + 1]:l += 1while r - 1 >= l and nums[r] == nums[r - 1]:r -= 1l += 1r -= 1return 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;
};