Cinte's Leetcode Record
0%

15. 3Sum

Posted on Edited on In Disqus:
Symbols count in article: 2.4k Reading time ≈ 2 mins.

15. 3Sum

自己的**方法
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
36
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ret;
        if(nums.size() < 3) return ret;
        sort(nums.begin(),nums.end());
        if(nums[0] > 0) return ret;
        int bias = 0;
        unordered_set<int> nummm;
        for(auto& num : nums)
        {
            if(nummm.find(num) != nummm.end())
            {
                ++bias;
                continue;
            }else
            {
                nummm.insert(num);
            }
            unordered_set<int> set;
            int target = -num;
            for(size_t i = ++bias; i < nums.size(); ++i)
            {
                if(set.find(target - nums[i]) != set.end())
                {
                    ret.push_back({-target, target - nums[i], nums[i]});
                    set.insert(nums[i]);
                    while(i + 1 < nums.size() && nums[i] == nums[i + 1]) ++i;
                    continue;
                }
                set.insert(nums[i]);
            }
        }
        return ret;
    }
};
改
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
36
37
class Solution
{
public:
    vector<vector<int>> threeSum(vector<int> &nums)
    {
        vector<vector<int>> ret;
        if (nums.size() < 3)
            return ret;
        sort(nums.begin(), nums.end());
        if (nums[0] > 0)
            return ret;
        int bias = 0;
        for (size_t i = 0; i < nums.size(); ++i)
        {
            while (i != 0 && nums[i] == nums[i - 1] && i + 1 < nums.size())
            {
                ++i;
                ++bias;
            }
            unordered_set<int> set;
            int target = -nums[i];
            for (size_t i = ++bias; i < nums.size(); ++i)
            {
                if (set.find(target - nums[i]) != set.end())
                {
                    ret.push_back({-target, target - nums[i], nums[i]});
                    set.insert(nums[i]);
                    while (i + 1 < nums.size() && nums[i] == nums[i + 1])
                        ++i;
                    continue;
                }
                set.insert(nums[i]);
            }
        }
        return ret;
    }
};
discussion里的O(n^2)方法
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
36
37
38
39
class Solution
{
public:
    vector<vector<int>> threeSum(vector<int> &nums)
    {
        vector<vector<int>> ret;
        sort(nums.begin(), nums.end());
        int n = nums.size();
        if(n < 3 || nums.front() > 0)
            return {};
        for (size_t i = 0; i < n; ++i)
        {
            if(i > 0 && nums[i] == nums[i - 1]) 
                continue;
            int low = i + 1, high = n - 1;
            int num = -nums[i];
            while (low < high)
            {
                if (nums[low] + nums[high] == num)
                {
                    ret.push_back({nums[i], nums[low], nums[high]});
                    while (low < high && nums[low] == nums[low + 1])
                        ++low;
                    while (low < high && nums[high] == nums[high - 1])
                        --high;
                    ++low;
                    --high;
                }else if(nums[low] + nums[high] < num)
                {
                    ++low;
                }else
                {
                    --high;
                }
            }
        }
        return ret;
    }
};