題目

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

題目連結

Example 1

1
2
3
4
5
6
7
8
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation: 
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

Example 2

1
2
3
Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.

Example 3

1
2
3
Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.

解釋題目

題目會給一個 integer array nums。

在 nums 內，找三個元素: [nums[i], nums[j], nums[k]]，i、j、k 不相等，且nums[i] + nums[j] + nums[k] == 0。

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

思路

  1. 先排序 nums，之後做雙指針比較好處理。
  2. 固定一項元素，並設成負數。再利用雙指針，找到剩下符合題意的元素。
    • Ex: nums[i] = 5 => -5 固定的元素
    • 利用雙指針找到 nums[j] + nums[k] = -5 => nums[i] + nums[j] + nums[k] == 0。
  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
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());

        vector<vector<int>> result;
        for(int i = 0; i < nums.size(); i++){
            int fix = -nums[i];
            int left = i + 1;
            int right = nums.size() - 1;

            while(left < right){
                if(nums[left] + nums[right] == fix){
                    vector<int> temp{nums[i], nums[left], nums[right]};
                    result.push_back(temp);
                    left++;
                    right--;
                    // 避免重複項，記得檢查邊界
                    while(left<right && nums[left]==nums[left-1]) left++;
                    while(left<right && nums[right]==nums[right+1]) right--;

                }else if(nums[left] + nums[right] > fix) // 代表總和太大
                    right--;
                else if(nums[left] + nums[right] < fix) // 代表總和太小
                    left++;
            }

            // 避免重複項，記得檢查邊界
            while(i+1 < nums.size() && nums[i] == nums[i+1])
                i++;
        }

        return result;
    }
};