---
image: https://leetcode.com/static/images/LeetCode_Sharing.png
tags: leetcode
---
# Week.3.MID [15. 3Sum]
---
- 一串數列, 找出三個數字加起來為0
---
- [參考](https://leetcode.com/problems/3sum/solutions/7392/python-easy-to-understand-solution-o-n-n-time/)
- i從0~length-2, 只做到兩個pointer之前
- l r 左右指標，開掃
- 如果這次i數字跟上次一樣跳過
- l or r 遇到一樣數字也跳過
- 也有看到另一個思路清晰的[分門別類的做法](https://leetcode.com/problems/3sum/solutions/725950/python-5-easy-steps-beats-97-4-annotated/)
---

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()
        # i iter 減去兩個pointer的數量
        for i in range(len(nums)-2):
            # 如果這次i數字跟上次一樣跳過
            if i > 0 and nums[i] == nums[i-1]:
                continue
            # 左右指標，開掃
            l, r = i+1, len(nums)-1
            while l < r:
                s = nums[i] + nums[l] + nums[r]
                if s < 0:
                    l +=1 
                elif s > 0:
                    r -= 1
                else:
                    res.append((nums[i], nums[l], nums[r]))
                    # append後, 遇到相同數字狂跳
                    while l < r and nums[l] == nums[l+1]:
                        l += 1
                    while l < r and nums[r] == nums[r-1]:
                        r -= 1
                    l += 1; r -= 1
        return res

[15. 3Sum]:https://leetcode.com/problems/3sum/description/