---
# System prepended metadata

title: '**Leetcode筆記(3Sum)**'
tags: [arrays, medium, microsoft, leetcode]

---

# **Leetcode筆記(3Sum)**


:::info
:information_source: 題目 : 3Sum, 類型 : arrays , 等級 : medium
日期 : 2023/02/21，2023/05/02，2023/06/27，2023/11/25，2023/12/08，2024/05/21，2025/02/14
:::


### 嘗試

繼續暴力解法，時間複雜度O(n^3)

```python
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        output = set()
        for n in nums:
            output.add(n)
        
        for i in range(len(output)):
            for j in range(len(output)):
                for p in range(len(output)):
                    if output[i] + output[j] + output[p] == 0 :
                        return output[i], output[j], output[p]
```
2023/05/02
```python
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = list()
        nums.sort()

        for i in range(0, len(nums)):
            # 防止nums[i]自己重複
            # 要有i>=1的限制 就能夠在nums = [0,0,0,0]
            # 只通過[[0,0,0]]而不是[[0,0,0],[0,0,0]]
            if i >= 1 and nums[i] == nums[i - 1]:
                continue

            l = i + 1
            r = len(nums) - 1
            
            while l < r:
                # 達到目標值
                if nums[l] + nums[r] + nums[i] == 0:
                    res.append([nums[l], nums[r], nums[i]])
                    # 沒想到要再更新 或遇到重複的要繼續往下一格走
                    l += 1
                    # 遇到兩個重複數字時
                    # 要用減的 不然可能會超出範圍
                    while nums[l] == nums[l - 1] and r > l:
                        l += 1

                elif nums[l] + nums[r] + nums[i] < 0:
                    l += 1
                else:
                    r -= 1
        
        return res
```
2023/06/27
用排序 + 雙指針輔助，主角數字用for迴圈跑，其他兩個數字用雙指針，要注意最後要輸出的是數字(重複的數字不算)，所以主角數字和l, r都要加入nums[i - 1] == nums[i]判斷，若相同則跳過
```python
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort() 
        res = []

        for i, n in enumerate(nums):
            # 不能有重複的(n這個主體數字)
            # 至少第一個要可以跑進迴圈
            if i > 0 and nums[i - 1] == nums[i]:
                continue
            l, r = i + 1, len(nums) - 1
            while l < r:
                if n + nums[l] + nums[r] < 0:
                    l += 1
                elif n + nums[l] + nums[r] > 0:
                    r -= 1
                else:
                    res.append([n, nums[l], nums[r]])
                    l += 1 # 換到一個完全不一樣的數字試試看
                    r -= 1
                    # 不能有重複的(l, r)
                    while nums[l - 1] == nums[l] and l < r:
                        l += 1
                    while nums[r + 1] == nums[r] and l < r:
                        r -= 1 

        return res
```
2023/11/25
```python
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res = []
        for i in range(len(nums)):
            if i - 1 >= 0 and nums[i] == nums[i - 1]:
                continue
            l, r = i + 1, len(nums) - 1
            while l < r:
                if nums[l] + nums[r] + nums[i] < 0:
                    l += 1
                elif nums[l] + nums[r] + nums[i] > 0:
                    r -= 1
                else: # equal to 0
                    res.append([nums[l], nums[r], nums[i]])
                    l += 1
                    r -= 1
                    while l < len(nums) and nums[l] == nums[l - 1]:
                        l += 1
                    while r >= 0 and nums[r] == nums[r + 1]:
                        r -= 1

        return res
```
2023/12/08
```python
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res = []

        for i, n in enumerate(nums):
            if i >= 1 and nums[i] == nums[i - 1]:
                continue
            l, r = i + 1, len(nums) - 1
            target = -n
            while l < r:
                if nums[l] + nums[r] > target:
                    r -= 1
                elif nums[l] + nums[r] < target:
                    l += 1
                else:
                    res.append([n, nums[l], nums[r]])
                    preL, preR = nums[l], nums[r]
                    l, r = l + 1, r - 1
                    while l < len(nums) and nums[l] == preL:
                        l += 1
                    while r > i and nums[r] == preR:
                        r -= 1
        
        return res
```
2024/05/21
第一個條件
```python
if 0 < i and nums[i] == nums[i - 1]:
    continue
記得要大於0，不然[0,0,0]第一個就跑不過

while l < r and nums[l] == nums[l - 1]:
    l += 1
while l < r and nums[r] == nums[r + 1]:
    r -= 1
記得這邊也要檢查邊界條件，因為在while裡面可能不停跑，不會跑到最上面的檢查
```

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

        for i, n in enumerate(nums):
            l, r = i + 1, len(nums) - 1
            if 0 < i and nums[i] == nums[i - 1]:
                continue
            while l < r:
                total = n + nums[l] + nums[r]
                if total > 0:
                    r -= 1
                elif total < 0:
                    l += 1
                else:
                    res.append([n, nums[l], nums[r]])
                    l += 1
                    r -= 1
                    while l < r and nums[l] == nums[l - 1]:
                        l += 1
                    while l < r and nums[r] == nums[r + 1]:
                        r -= 1

        return res
```

2025/02/14




---
### **優化**

若目前的sum<0，我們想要sum變大，故移動l指針，因為l指針必小於r指針，反之亦然
時間複雜度 sort為O(nlogn)+兩個指針forO(n^2) = O(n^2) ，空間複雜度O(n)

```python
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()
        
        for i, n in enumerate(nums):
            if i >= 1 and n == nums[i-1]: # 每一個新的n才會跑來檢查
                continue
            r = len(nums) - 1
            l = i + 1
            while r > l: # 每個n才會開始跑它後面的r l 
                threeSum = n + nums[r] + nums[l]
                if threeSum > 0:
                    r = r - 1
                elif threeSum < 0:
                    l = l + 1
                else:
                    res.append([n, nums[r], nums[l]])
                    l = l + 1 # 要讓l再自動往右 不然會無限循環
                    while nums[l] == nums[l-1] and r > l: # 需再移一格 否則會有重複的res
                        l = l + 1  
        return res
```
---


**:warning: 錯誤語法** 
:::warning
嘗試後得到錯誤語法'set' object is not subscriptable
*此行if output[i] + output[j] + output[p] == 0 :
set加元素set.add()
:::


**:thumbsup:學習** 
:::success
```python
# sorted是複製新的一份進行排序，
A = [1,3,5,1,2]
B = sorted(A)
# .sort()是直接在原list排序(所以沒有回傳)
A = [1,3,5,1,2]
A.sort()
```
break：強制跳出 ❮整個❯ 迴圈
continue：強制跳出 ❮本次❯ 迴圈，繼續進入下一圈
pass：不做任何事情，所有的程式都將繼續

sort為O(nlogn)

有重複的語法就用一個東西代替，寫一次就好

list.append() 如res.append([n, nums[r], nums[l]])
:::

**思路**
![](https://i.imgur.com/TqFfiE0.png)


**講解連結**
https://www.youtube.com/watch?v=jzZsG8n2R9A
Provided by. NeetCode

###### tags: `arrays` `leetcode` `medium`