15. 3Sum

  • Hardness: \(\color{orange}\textsf{Medium}\)
  • Ralated Topics: Array、Two Pointer、Sorting

一、題目

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.

Example 1:

  • 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:

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

Example 3:

  • Input: nums = [0,0,0]
  • Output: [[0,0,0]]
  • Explanation: The only possible triplet does sum up to 0.

Constraints:

  • 3 <= nums.length <= 3000
  • -10^5 <= nums[i] <= 10^5

二、分析

  • 若用暴力解求解的話，時間複雜度為 \(O(n^3)\)。
  • 故我們可以嘗試先進行排序來簡化問題，時間複雜度為\(O(n\log n)\)。
  • 方法 1: HashMap
    • 可以參考 Leetcode no.1 Two Sum，相當於一個迴圈選定 nums[i] 為 target，其餘兩者 nums[j] + nums[k] 的和為 -target，那這題就簡化成 Two Sum 了，時間複雜度為 \(O(n^2)\)。
  • 方法 2: Two Pointer
    • 同樣一個迴圈選定 nums[i] 為 target，其餘兩者以 Two Pointer 搜尋已排序的數組。
  • 需注意上如何避免重複數組解：
    • HashMap 可以直接指定到 HashMap 存的索引，利用 HashMap 會覆蓋掉同一組 key 的 value。
    • Two Pointer 可以藉由指標指向同一個值時，便跳過，來避免重複數組解。

三、解題

1. HashMap

  • Time complexity: \(O(n^2)\)
  • Space complexity: \(O(n)\)
vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());     // 排序
    unordered_map<int,int> map;
    vector<vector<int>> res;
    for (int i = 0; i < nums.size(); i++) {
        map[nums[i]] = i;   // 將值「最右邊」的索引記到 map 中
    }
    for (int i = 0; i < nums.size()-2; i++) {
        for (int j = i+1; j < nums.size()-1; j++) {
            int toFind = -(nums[i] + nums[j]);
            if (toFind < 0) continue;   // 若 nums[i] 與 num[j] 的和為正時，無解。
            if (map.find(toFind) != map.end() && map[toFind] > j) {     // 注意 map 中找到的值的索引，必須比第二個值的索引大
                res.push_back({nums[i], nums[j], toFind});
            }
            j = map[nums[j]];   // 避免重複數組解
        }
        i = map[nums[i]];   // 避免重複數組解
    }
    return res;
}

2. Two Pointer

  • Time complexity: \(O(n^2)\)
  • Space complexity: \(O(1)\)
vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());     // 排序
    vector<vector<int>> res;
    for (int i = 0; i < nums.size()-2; i++) {
        if (nums[i] > 0) break;         // 排序後，三數組中最小的值若為正，則無解
        int j = i+1, k = nums.size()-1;
        while (j < k) {
            int sum = nums[i] + nums[j] + nums[k];
            if (sum < 0) {              // 三數組合小於零，左指標右移。
                while (j+1 < k && nums[j] == nums[j+1]) j++;    // 優化，同樣的值不需重複檢查
                j++;
            } else if (sum > 0) {       // 三數組合大於零，右指標左移。
                while (k-1 > j && nums[k-1] == nums[k]) k--;    // 優化，同樣的值不需重複檢查
                k--;
            } else {
                res.push_back({nums[i], nums[j], nums[k]});
                while (j+1 < k && nums[j] == nums[j+1]) j++;    // 避免重複數組解
                while (k-1 > j && nums[k-1] == nums[k]) k--;    // 避免重複數組解
                j++;
                k--;
            }
        }
        while (i+1 < nums.size()-2 && nums[i] == nums[i+1]) i++;    // 避免重複數組解
    }
    return res;
}

參考文章: [LeetCode] 18. 4Sum
回目錄 Catalog