題目資訊

題目編號: 15
題目連結: 3Sum
主題: Array, Two Pointers, Sorting

題目敘述

給定一個整數陣列 nums，找出所有使 $[nums[i], nums[j], nums[k]]$ 滿足 $i \neq j$，$i \neq k$，$j \neq k$，並且 $nums[i] + nums[j] + nums[k] = 0$ 的三元組。

請注意，解集不得包含重複的三元組。

範例 1:

輸入： nums = [-1,0,1,2,-1,-4]
輸出： [[-1,-1,2],[-1,0,1]]
解釋：
$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$.
不同的三元組為 [-1,0,1] 和 [-1,-1,2]。
請注意，輸出順序和三元組的順序不重要。

範例 2:

輸入： nums = [0,1,1]
輸出： []
解釋： 唯一可能的三元組無法相加為 0。

範例 3:

輸入： nums = [0,0,0]
輸出： [[0,0,0]]
解釋： 唯一可能的三元組相加為 0。

約束條件：

$3 \leq nums.length \leq 3000$
$-10^5 \leq nums[i] \leq 10^5$

直覺

這個問題要求尋找數組中所有和為零的唯一三元組。一個直接的方法是使用暴力解法，檢查數組中每一個可能的三元組組合。然而，這樣的做法在計算上是昂貴的，其時間複雜度為 $O(n^3)$。取而代之的是，可以通過將數組排序並使用雙指針技術來實現更高效的解法，從而將複雜度降低到 $O(n^2)$。排序有助於識別潛在組合並有效地避免重複。

解法

數組排序： 首先對輸入數組 nums 進行排序。排序是至關重要的，因為它使我們能夠更有效地應用雙指針技術。雖然考慮數字的和時元素的順序並不重要，但排序有助於輕鬆地管理和跳過重複的元素。
遍歷數組： 循環遍歷數組中的每個元素，直到倒數第三個元素，因為我們至少需要三個元素來構成一個三元組。
雙指針技術： 對於每個在索引 i 上的元素，設定兩個指針——left 初始化為 i + 1，right 初始化為數組的最後一個索引。這些指針將幫助找到另外兩個數，其和與 nums[i] 為零。
和的計算與調整：
- 計算三元組 nums[i] + nums[left] + nums[right] 的和。
- 如果和大於零，減小 right 指針以縮小和。
- 如果和小於零，增大 left 指針以增加和。
- 如果和等於零，則找到一個有效的三元組。將這個三元組加入結果集中，並調整 left 和 right 指針以繼續尋找其他可能的三元組。確保跳過重複值來保持三元組的唯一性，避免重複的元素。
避免重複：
- 在處理一個潛在的三元組之後，移動 left 和 right 指針過任何重複的數，確保新位置的 left 和 right 指向與先前不同的元素。
- 此外，跳過任何重複的起始元素 nums[i]，以防止形成多次相同的三元組。
返回結果： 檢查所有可能的三元組後，返回結果列表，其中包含所有和為零的唯一三元組。

這個方法利用排序和雙指針技術來有效探索可能的組合，並通過避免重複保持結果的唯一性，提供了一個時間複雜度為 $O(n^2)$ 的最佳解法。

程式碼

C++

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        // 用於儲存結果三元組的向量
        vector<vector<int>> result;
        
        // 將數組排序以方便使用雙指針方法
        sort(nums.begin(), nums.end());

        // 遍歷數組中的每個元素
        for (int i = 0; i < static_cast<int>(nums.size()) - 2; i++) {
            int left = i + 1;  // 初始化左指針
            int right = nums.size() - 1;  // 初始化右指針
            
            // 若有可能形成三元組
            while (left < right) {
                // 計算三元組的和
                int sum = nums[i] + nums[left] + nums[right];
                
                if (sum > 0) {
                    // 若和大於零則遞減右指針
                    do {
                        right--;
                    } while (left < right && nums[right] == nums[right + 1]);  // 避免重複元素
                } else if (sum < 0) {
                    // 若和小於零則遞增左指針
                    do {
                        left++;
                    } while (left < right && nums[left] == nums[left - 1]);  // 避免重複元素
                } else {
                    // 若和等於零則將三元組加入結果
                    result.push_back(vector<int>{nums[i], nums[left], nums[right]});
                    
                    // 移動兩個指針並避免兩端的重複元素
                    do {
                        left++;
                    } while (left < right && nums[left] == nums[left - 1]);
                    do {
                        right--;
                    } while (left < right && nums[right] == nums[right + 1]);
                }
            }
            // 避免考慮 nums[i] 的相同值，通過跳過重複元素
            while (i < static_cast<int>(nums.size()) - 2 && nums[i] == nums[i + 1]) i++;
        }
        
        return result;
    }
};

Python

class Solution:
    def threeSum(self, nums):
        # 用來存儲結果三元組的列表
        result = []
        
        # 將列表排序以便使用雙指標方法
        nums.sort()

        # 遍歷列表中的每個元素
        for i in range(len(nums) - 2):
            left = i + 1  # 初始化左指標
            right = len(nums) - 1  # 初始化右指標
            
            # 當有可能形成三元組時
            while left < right:
                # 計算三元組的和
                sum_ = nums[i] + nums[left] + nums[right]
                
                if sum_ > 0:
                    # 如果和大於零則遞減右指標
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1  # 避免重複元素
                    right -= 1
                elif sum_ < 0:
                    # 如果和小於零則遞增左指標
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1  # 避免重複元素
                    left += 1
                else:
                    # 如果和等於零，則將三元組加入結果中
                    result.append([nums[i], nums[left], nums[right]])
                    
                    # 移動兩個指標並避免兩端的重複
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    left += 1
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1
                    right -= 1
            
            # 通過跳過重複項來避免考慮相同值的 nums[i]
            while i < len(nums) - 2 and nums[i] == nums[i + 1]:
                i += 1
        
        return result

複雜度分析

時間複雜度: $O(n^2)$

時間複雜度的主要組成部分包括排序數組和尋找三元組的巢狀迴圈。排序數組需要的時間是 $O(n \log n)$，其中 $n$ 是數組的長度。尋找三元組的巢狀迴圈結構在最壞情況下是 $O(n^2)$，因為我們對每個元素使用兩個指針來迭代整個數組。因此，整體的時間複雜度是 $O(n \log n + n^2)$。由於對於較大的 $n$，$n^2$ 對 $n \log n$ 具有主導地位，所以時間複雜度被簡化為 $O(n^2)$。

空間複雜度: $O(n)$

空間複雜度主要是由於存儲所需的輸出，在最壞情況下，最多可以存儲 $O(n)$ 個三元組。排序所使用的空間是 $O(1)$ 如果使用原地算法，或者是 $O(n)$ 如果不是，但相比於存儲結果所使用的空間，這通常被認為是可以忽略的。因此，整體的空間複雜度是 $O(n)$。

CS Note
En

Leetcode 15. 3Sum

題目資訊

題目敘述

直覺

解法

程式碼

C++

Python

複雜度分析