Leetcode 15. 3Sum

3Sum : 給一個數組nums，判斷nums中是否存在3個元素a,b,c，使得a+b+c=0，找出所有滿足條件且不重覆得所有組合。

首先sort nums，如果第一個數大於0不會有解，如果連續兩個一樣的數，則countinue不用找，之後j<k來找到所有的值，如果合小於0，希望他大一點j+1，如果合大於0，希望他小一點k-1，找到答案後，去除重複值，最後返回結果。

時間複雜度: O(N^2)

空間複雜度: O(1)

Python

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n=len(nums)
        nums.sort()
        l=[]
        
        for i in range(n-1):
            if nums[i]>0:                     #如果第一個數大於0不會有解
                break
            if i>0 and nums[i]==nums[i-1]:    #連續兩個一樣的數，不用找
                continue
            j=i+1                             #最小的數
            k=n-1                             #最大的數
            while j<k:
                cur=nums[i]+nums[j]+nums[k]   #三數之和
                if cur<0:                     #合小於0，希望他大一點
                    j+=1
                elif cur>0:                   #合大於0，希望他小一點
                    k-=1
                else:
                    l.append([nums[i],nums[j],nums[k]])   #答案
                    while j+1<k and nums[j]==nums[j+1]:   #去除重複值
                        j+=1
                    while k-1>j and nums[k]==nums[k-1]:   #去除重複值
                        k-=1
                    j+=1
                    k-=1
        return l

C++

class Solution {
public:
  vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> ans;
    std::sort(nums.begin(), nums.end());
    const int n = nums.size();
    for (int i = 0; i < n - 2; ++i) {
      if (nums[i] > 0) break;
      if (i > 0 && nums[i] == nums[i - 1]) continue;  #連續兩個一樣的數
      int l = i + 1;
      int r = n - 1;      
      while (l < r) {
        if (nums[i] + nums[l] + nums[r] == 0) {    #三數之和
          ans.push_back({nums[i], nums[l++], nums[r--]});
          while (l < r && nums[l] == nums[l - 1]) ++l;
          while (l < r && nums[r] == nums[r + 1]) --r;          
        } else if (nums[i] + nums[l] + nums[r] < 0) {
          ++l;    #合小於0，左端右移
        } else {  
          --r;    #合大於0，右端左移
        }
      }
    }
    return ans;
  }
};