###### tags: `Leetcode` `medium` `pointer` `python` `Top 100 Liked Questions`

# 15. 3Sum

## [題目連結:] https://leetcode.com/problems/3sum/

## 題目:
Given an integer array nums, return all the triplets ```[nums[i], nums[j], nums[k]]``` such that ```i != j, i != k,``` and ```j != k```, and ```nums[i] + nums[j] + nums[k] == 0```.

Notice that the solution set must not contain duplicate triplets.

**Example 1:**

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation: 
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

Example 2:

Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.

Example 3:

Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.

## 解題想法:
兄弟題目: [16. 3Sum Closest](/-2KGuo22S3qNrqbNTpvC_w)、[18. 4Sum](/DxMPstejSjGGRPi7EHckdA)
* 題目要求: 給一數組，要求三數和=0，且每種組合不能重複
* use two pointer
* for 迴圈固定一值(i)
* 找two pointer(j、k)與i之nums[i]+nums[j]+nums[k]=0
* j=i+1
* k=len(nums)
* 因為避免找重複的組合，所以**數組一定要先排序**!!
* 優化:因為是排序好再找，因此nums[i]一定是最小值，若nums[i]>0，則一定沒解了，因為nums[j]、nums[k]一定更大，可直接break

## python:
time:O(nlongn+n^2) space:O(1)

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        #use two pointer
        res =[]
        #一定要先排序
        nums.sort()
        for i in range(len(nums)-2):
            #和為0 sort完 jk在i後面 若i都>0了 肯定沒搞頭了
            if nums[i]>0:
                break
            #若遇重複i，只能使用第一次出現的  所以跳過此輪
            #因為確保i=0與i=1時nums[i]相同值時 要優先用i=0 所以要規定判別於i>0
            if i>0 and nums[i]==nums[i-1]:
                continue
            j = i+1
            k = len(nums)-1
            while j<k:
                #nums之i+j+k值為0 fuck ya
                if nums[i]+nums[j]+nums[k]==0:
                    res.append([nums[i],nums[j],nums[k]])
                    j+=1
                    k-=1
                    #跳過重複的nums[j]
                    while j<k and nums[j]==nums[j-1]:
                        j+=1
                    #跳過重複的nums[k]
                    while j<k and nums[k]==nums[k+1]:
                        k-=1
                #總值過小 增加j
                elif nums[i]+nums[j]+nums[k]<0:
                    j+=1
                #總值過大 減k
                else:
                    k-=1
        return res

if __name__ == '__main__':
    result = Solution()
    nums = [-1,0,1,2,-1,-4]
    ans = result.threeSum(nums)
    print(ans)