15. 3Sum

題目網址：https://leetcode.cn/problems/3sum/

題意：給一整數 array nums, 返回 nums 是否存在 [nums[i], nums[j], nums[k]], 使得 nums[i] + nums[j] + nums[k] == 0, 其中 i != j, i != k 且 j != k。

注意：答案中不可包含重複的 tuple。

Solution：

想法：利用 Two Pointers

• 首先, 將 nums 由小到大做排序

  • 用來避免取重複的 tuple, 並可使用 two pointer 來移動 ptr

• 用 i 遍歷 index = [0, n - 3], 得到 nums[i]

  • 為了避免第一次取到與上一輪相同的元素，我們需要在這裡進行一次判斷並跳過
  • 使用 Two pointer left = i + 1, right = n - 1 尋找滿足條件的 pair
  • 若 sum < 0 : 則 left + 1
  • 若 sum > 0 : 則 right - 1
  • 若 sum == 0 : 則將 tuple 加入到 res 中，由於還要檢查剩餘的元素中是否有滿足條件的。因此在加入 tuple 後，left 和 right 都需要跳過與當前元素相同的值

• 注意：答案中不可包含重複的 tuple

  • 對於第一個元素，我們在判斷時已經確保不會與上一輪相同
  • 對於第二和第三個元素，在加入 res 後，我們繼續遍歷剩餘元素時，需要判斷是否與上一個元素相同，如果相同則跳過

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        const int n = nums.size();

        sort(nums.begin(), nums.end());

        vector<vector<int>> res;
        for (int i = 0; i < n - 2; ++i) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            int left = i + 1, right = n - 1;

            while (left < right) {
                const int sum = nums[i] + nums[left] + nums[right];

                if (sum > 0) {
                    --right;
                } else if (sum < 0) {
                    ++left;
                } else {
                    res.emplace_back(vector<int>{nums[i], nums[left], nums[right]});

                    // skip duplicates for the second element
                    while (left < right && nums[left] == nums[left + 1]) {
                        ++left;
                    }

                    // skip duplicates for the third element
                    while (left < right && nums[right] == nums[right - 1]) {
                        --right;
                    }

                    // move pointers to the next elements with different values
                    ++left;
                    --right;
                }
            }
        }
        return res;
    }
};

• time：$O(n^2)$ ➔ $O(n \cdot log(n))$ + $O(n^2)$
  • $O(n \cdot log(n))$ : 排序 nums
  • $O(n^2)$ : for loop 需 $O(n)$, 其中每一個元素用 two ptr 遍歷剩餘元素需 $O(n)$
• space：$O(1)$ ➔ 若不考慮 output array, 只需常數空間