題目

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

  • 0 <= a, b, c, d < n
  • a, b, c, and d are distinct.
  • nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

題目連結

Example 1

1
2
Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Example 2

1
2
Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]

解釋題目

題目會給一個 integer array nums，和一個 integer targets。

在 nums 內，找四個元素: [nums[a], nums[b], nums[c], nums[d]]，a、b、c、d 不相等，且nums[a] + nums[b] + nums[c] + nums[d] == target。

這種四元素可能會有很多個，回傳所有可能，但不要回傳重複的答案。

這題跟 Leetcode-15 很像。

思路

  1. 先排序 nums，之後做雙指針比較好處理。
  2. 固定前兩個元素(i、j)，再利用雙指針，找到剩下符合題意的元素。(和 3Sum 相同)
  3. 為了避免重複，確認發現了一組解之後，再移動 left 和 right 指針，略過重複項。

程式碼

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
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());

        for(int i = 0; i < nums.size(); i++){
            
            for(int j = i + 1; j < nums.size(); j++){
                int left = j + 1;
                int right = nums.size() - 1;
                while(left < right){
                    // 要用 long long，否則會 overflow
                    long long sum = (long long)nums[i] + nums[j] + nums[left] + nums[right];
                    if(sum == target){
                        result.push_back({nums[i], nums[j], nums[left], nums[right]});
                        left++;
                        right--;
                        
                        // 避免重複項
                        while(left<right && nums[left] == nums[left-1]) left++;
                        while(left<right && nums[right] == nums[right+1]) right--;
                    }else if(sum < target)
                        left++;
                    else if(sum > target)
                        right--;
                }
                // 避免重複項
                while(j+1<nums.size() && nums[j+1]==nums[j]) j++;
            }
            // 避免重複項
            while(i+1<nums.size() && nums[i+1]==nums[i]) i++;
        }
        
        return result;
    }
};

// target: 0
// -2, -1, 0, 0, 1, 2

Reference

贾考博 LeetCode