➣ Reading Time: 12 minutes

題目出處

https://leetcode.com/problems/3sum/

難度

Medium

題目分類

Array, TwoPointers

個人手繪解法筆記 (解法重點)

這題是第 1 題的延伸題目,這次我們要處理 3數之和 的問題。

大概念

我們將這個題目看成,「任兩數和」 等於 「負的第三數」
「負的第三數」我們稱之為我們要的 target
為了更乾淨我們處理的順序,我們會先進行「排序」

示意圖:

TwoPointers

在排序後,我們選定 target,我們使用 TwoPointers,
從左 ( l ) 開始小往大掃、從右 ( r ) 開始大往小掃,
當左( l ) 大於等於右( r ) ,也就是交錯甚至超過。
就是我們的終止條件。

示意圖:

重複處理 case1 : target 的重複

重複時的選擇:我們選擇第一個 target。

除了 target 重複會造成重複解答之外,
選擇第一個也能夠保證當解答中有與target重複的數值也能被我們考慮到。

  • 示意圖:(處理 target 的重複)

  • 可以觀察 i 與 target 的變化,仔細思考,可以得到一些心得:

重複處理 case2 : r, l 選到值的重複

  • 重複時的選擇:我們選擇「l」的第一個值,r不同時處理。

因為,當我們得到答案並更新「l」之後,對應的 nums[r] 直接不成立。
思考時,只需要思考單邊重複如何處理即可。 (多思考會錯,可以見下面錯誤區)

選擇第一個值的原因是,我們預期「剩下的值」有可能存在答案。
當找到答案時,我們再將「l」移至下一個值 (也就是說,反覆 l+1 直到值不同)

這樣才能處理極端狀況:[0, 0, 0]

  • 示意圖:(處理 l, r 的重複)

個人範例程式碼

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        ans = []

        # decide target
        for i in range(len(nums)):
            if(i > 0 and nums[i-1] == nums[i]): # when same target, only calculate first 
                continue # go to next loop
            target = -nums[i]
            # print(f"i = {i}, target = {target}") # debug

            l = i+1
            r = len(nums)-1

            while(l < r and l < len(nums) and r >= 0): # normal condition
                # print(f"l = {l}, r = {r}") # debug
                if nums[l] + nums[r] == target:
                    ans.append([nums[i], nums[l], nums[r]])
                    l += 1
                    while l < r and nums[l] == nums[l-1]: # when same value, only calculate first
                        l += 1 
                elif nums[l] + nums[r] > target: # need smaller, r - 1
                    r -= 1                  
                else: # nums[l] + nums[r] < target: need bigger, l + 1
                    l += 1        

        return ans

「錯誤紀錄」 手繪筆記

重點:錯誤錯在兩邊同時尋找,無法解[0,0,0] 這個 case!

這題是第 1 題的延伸題目,這次我們要處理 3數之和 的問題。

大概念

我們將這個題目看成,「任兩數和」 等於 「負的第三數」
「負的第三數」我們稱之為我們要的 target
為了更乾淨我們處理的順序,我們會先進行「排序」

示意圖:

TwoPointers

在排序後,我們選定 target,我們使用 TwoPointers,
從左 ( l ) 開始小往大掃、從右 ( r ) 開始大往小掃,
當左( l ) 大於等於右( r ) ,也就是交錯甚至超過。
就是我們的終止條件。

示意圖:

重複處理 case1 : target 的重複

重複時的選擇:我們選擇第一個 target。

除了 target 重複會造成重複解答之外,
選擇第一個也能夠保證當解答中有與target重複的數值也能被我們考慮到。

示意圖:

重複處理 case2 : r, l 選到值的重複

重複時的選擇:我們選擇最後一個值。

選擇最後一個值的原因是,我們預期「剩下兩個值」的組合應該會不同。
所以我們只看最後一個。

而且,就算真的重複了。(例如極端狀況:[0, 0, 0]) (此方法並沒有辦法處理)
我們也會先進行 -target = nums[l] + nums[r] 的檢查後,
抓出這樣的極端情況。

示意圖:

Reference

https://leetcode.com/problems/3sum/discuss/7498/Python-solution-with-detailed-explanation

⭐Python leetcode 相關文章整理⭐:
⭐Leetcode 解題紀錄⭐:難度Tag
⭐面試最經典 Top 75 題⭐:
1.【Leetcode】python - [1] Two Sum 兩數之和 個人手繪解法筆記 (只講解法重點, 內含範例程式碼)#Easy#Array #HashTable
3.【Leetcode】python - [3] Longest Substring Without Repeating Characters 個人手繪解法筆記 (只講解法重點, 內含範例程式碼) #Medium#HashTable #TwoPointers #String #SlidingWindow
5.【Leetcode】python - [5] Longest Palindromic Substring 個人手繪解法筆記 (只講解法重點, 內含範例程式碼) #Medium#String #DP
11.【Leetcode】python - [11] Container With Most Water 個人手繪解法筆記 (只講解法重點, 內含範例程式碼) #Medium#Array #TwoPointers
15.【Leetcode】python - [15] 3Sum 三數之和 個人手繪解法筆記 (只講解法重點, 內含範例程式碼) #Medium#Array #TwoPointers
48.【Leetcode】python - [48] Rotate Image 旋轉矩陣 個人手繪解法筆記與解題思考建議 (只講解法重點, 內含範例程式碼)#Medium (但我覺得很難)#Array
104.【Leetcode】python - [104] Maximum Depth of Binary Tree 個人手繪解法筆記 (只講解法重點, 內含範例程式碼) #Easy#Tree #DFS #Recursion
⭐Leetcode 小技巧⭐:
1.【Python】python 測試程式 – 利用 doctest 測試 python testcase 的優雅寫法,適用於 leetcode (doctest in function,搭配 function 的用法)
2.【Leetcode】python – 利用 doctest 測試 leetcode python testcase 的優雅寫法 (doctest in class,搭配 class 的用法)
⭐【喜歡我的文章嗎? 歡迎幫我按讚~ 讓基金會請創作者喝一杯咖啡!
如果喜歡我的文章,請幫我在下方【按五下Like】 (Google, Facebook 免註冊),會由 「LikeCoin」 贊助作者鼓勵繼續創作,讀者們「只需幫忙按讚,完全不用出錢」哦!

likecoin-steps