雙指標的進階題型

題目連結: 15. 3Sum

題目描述:給定一個包含n 個整數的陣列 nums，請找出所有不重複的三元組 (i, j, k)，使得 i + j + k = 0。

核心規則：

1. 從陣列中找出三個數字。

2. 這三個數字的總和必須等於 0。

3. 最終的答案中，不可以包含重複的三元組。例如 [-1, 0, 1] 和 [0, 1, -1] 算是同一個三元組。

Python

最直接的想法就是：窮舉所有三個數字的組合，看看它們的和是不是 0。
演算法:

• 使用三層巢狀迴圈來遍歷所有可能的 (i, j, k) 組合。

• 檢查 nums[i] + nums[j] + nums[k] 是否等於 0。

• 如果等於 0，就將這個組合加入結果中。

• 最後，還需要對結果進行去除重複項處理，這一步本身也很耗時。

此演算法的時間複雜度是O(n^3)，空間複雜度O(m)，m是不同的三元組數量。

顯然不是我們要找的答案，它太慢了。

排序+雙指針

思路分析:尋找三個數 (a, b, c) 的問題，轉化為「固定一個數 a，然後在剩下的陣列中尋找兩個數 b, c」的問題。

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        ans =[]
        for i in range(len(nums)-2):
            x = nums[i]
            j = i+1
            k = len(nums)-1
            if i>0 and x == nums[i-1]:
                continue
            while j<k:
                s = x + nums[j] + nums[k]
                if s>0:
                    k-=1
                elif s<0:
                    j+=1
                else:
                    ans.append([x,nums[j],nums[k]])
                    j+=1
                    k-=1
                    while j<k and nums[j]==nums[j-1]:
                        j+=1
                    while j<k and nums[k]==nums[k+1]:
                        k-=1
        return ans
                

演算法分析:

• 先對陣列進行排序，排序後，陣列變為有序，較容易去做去重複的邏輯。
• 遍歷陣列，nums[i] 作為我們三元組中的第一個固定數字 x。
• pythonif i > 0 and x == nums[i-1]: continue如果陣列是 [4, -1, -1, 0, 1, 2]，當 i=1 時我們已經處理過以 -1 開頭的所有情況，那麼當 i=2 時，nums[i] 又是 -1，就沒有必要再做一次，因為結果會完全相同。
• 在固定了 nums[i] (即 x) 之後，我們的目標就變成了在 i 後面的子陣列中，尋找兩個數，它們的和等於 -x。
• i指向子陣列的頭，k指向子陣列的尾，接著進行比較。
• 當 s == 0 時，我們成功找到了一組解。不過此時還要將子陣列進行去除重複項處理。在找到一組解後，我們不能停在原地，因為 j 和 k 指向的數字可能在後面還有重複。例如，在 [-2, 0, 0, 2, 2] 中找到 [-2, 0, 2] 後，我們需要跳過後面重複的 0 和 2。
• 過程會持續到外層 for 迴圈結束，最終 ans 中就包含了所有不重複且和為零的三元組。

複雜度分析:
* 排序佔用了O(n log n)，後面邏輯佔用了O(n^2)，因為n^2>nlogn，所以時間複雜度為O(n^2)。
* 空間複雜度為O(1)(若考慮排序結果則空間複雜度為O(n)。

今天就介紹到這邊，有問題都可以留言
下回見!