# **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://www.youtube.com/watch?v=jzZsG8n2R9A
Provided by. NeetCode
###### tags: `arrays` `leetcode` `medium`
Sign in with Wallet
Connect another wallet