題目： LeetCode - 15. 3Sum

題目說明

給一個陣列，求此陣列中所有三個元素值相加為 0 的組合。

解題思路

為了增加效率，先對陣列進行排序，接著遍歷陣列，先選定一個最左邊的數字，接著往右找是否存在相加為此數的相反數的組合，若存在代表找到一組，接著檢查 l 的右邊及 r 的左邊的數是否相同，避免找到重複的組合。同時再過程中若是 nums[i] > 0 就可以不用再找了，因為我們是選定最左邊的數，且我們的陣列是排序過的，所以右邊不可能會有相加為此數的相反數的組合，同時要避免重複運算，所以若 nums[i] == nums[i - 1] 則直接 continue。

參考解法

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
// fast IO
static auto __ = []()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums)
    {
        int n = nums.size();
        vector<vector<int>> v;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < n - 2; ++i)
        {
            if (nums[i] > 0) break;
            if (i && nums[i] == nums[i - 1]) continue;
            int target = -nums[i], l = i + 1, r = n - 1;
            while (l < r)
            {
                if (nums[l] + nums[r] == target)
                {
                    v.push_back({ nums[i], nums[l], nums[r] });
                    // 避免儲存到一樣的結果
                    while(l < r && nums[l] == nums[l + 1]) ++l;
                    while(l < r && nums[r] == nums[r - 1]) --r;
                    ++l, --r;
                }
                else if (nums[l] + nums[r] < target) ++l;
                else --r;
            }
        }
        return v;
    }
};