15. 3Sum

發表於 | 分類於

problem

從陣列中，找出所有三個元素總和為零。

solution

  1. 先對原陣列進行排序
  2. 固定一個數i，再利用雙索引 j k 找出總和為 0-target[i]
  3. 找到後加左索引j 向右移一位，k 向左移一位。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ret;
        int n=nums.size();
        sort(nums.begin(), nums.end());
        for(int i=0;i<n-2;++i){
            // 確保不會重複
            if(i>0 && nums[i] == nums[i-1]) continue;
            int l = i+1, r = n-1;
            int target = -nums[i];
            while(l<r){
                int sum = nums[l] + nums[r];
                if(sum==target){
                    ret.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--;
                    l++;
                    r--;
                }
                 else if(sum<target) l++;
                else r--;
            }
        }
        return ret;
    }
};

analysis

  • time complexity O(n^2)
  • space complexity O(1)