首页 > 代码库 > 15. 3Sum

15. 3Sum

2024-08-25 18:44:53   220人阅读

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

分析

遍历每一个nums[i], 把它当作 twoSum 的 target number。

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
28
29
30
31
32
33
34
35
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int len = nums.size();
        vector<vector<int> > result;
        if (len < 3) return result;
        sort(nums.begin(), nums.end());
         
        for(int i = 0; i < len -2; i++){
            if(i > 0 && nums[i] == nums[i - 1]){
                continue;
            }
            int l = i + 1, r = len - 1;
            while(l < r){
                if( nums[l] + nums[r] + nums[i] > 0){
                    r--;
                }
                else if(nums[l] + nums[r] + nums[i] < 0){
                    l++;
                }
                else{
                    result.push_back(vector<int>{nums[i],nums[l],nums[r]});
                    l++;
                    while( l < r && nums[l] == nums[l - 1]){
                        l++;
                    }
                     
                }
            }
        }
         
        return result;
    }
     
};



来自为知笔记(Wiz)


15. 3Sum


联系
我们