【leetcode】3 SUM总结

阿里 阅读:328 2022-03-12 16:24:53 评论:0
本文章主要介绍了【leetcode】3 SUM,具有不错的的参考价值,希望对您有所帮助,如解说有误或未考虑完全的地方,请您留言指出,谢谢!

3 SUM

原题:

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] 
] 

题意

找到数组中三个数加起来的值等于0的所有集合。

思路:

2 SUM问题的解决方法是先将数组排序,前后分别一个指针向中间逼近,时间复杂度为O(NlogN)。所以3 SUM的做法可以模仿该做法,从数组中先取一个数t,再去用2 SUM的做法去获得剩下两个加和为-t的数。

有一个最大的问题是结果去重,可以有两个方法解决,首先想到的是用set数据结构,另一种方法是遇到结果相同的数直接跳过。

代码

使用set的方法

class Solution { 
public: 
    vector<vector<int>> threeSum(vector<int>& nums) { 
        sort(nums.begin(), nums.end()); 
        set<vector<int>> s; 
        for(int i = 0;i<nums.size();i++) 
        { 
			//如果第一个数已经大于0,可以不判断后面的数了,因为三个大于0的数不可能加起来等于0 
            if(nums[i] > 0) break; 
            vector<int> ans0(3,0); 
            ans0[0] = nums[i]; 
            int t = 0 - nums[i]; 
            int l = i+1, r = nums.size()-1; 
            while(l < r) 
            { 
                if(nums[l] + nums[r] == t) 
                { 
                    ans0[1] = nums[l]; 
                    ans0[2] = nums[r]; 
					//如果下一个数等于前一个数,跳过该数 
                    while(l<r && nums[l+1] + nums[r] == t) l++; 
                    while(l<r && nums[l] + nums[r+1] == t) r++; 
                    s.insert(ans0); 
                    l++; 
                    r--; 
                }else if(nums[l] + nums[r] < t) 
                    l++; 
                else 
                    r--; 
            } 
        } 
		//用set构造vector 
        vector<vector<int>> ans(s.begin(), s.end()); 
        return ans; 
    } 
}; 

不使用set:

class Solution { 
public: 
    vector<vector<int>> threeSum(vector<int>& nums) { 
        sort(nums.begin(), nums.end()); 
        vector<vector<int>> ans; 
        for(int i = 0;i<nums.size();i++) 
        { 
            if(nums[i] > 0) break; 
			//如果下一个数和当前数相等,跳过 
            if(i>0 && nums[i]==nums[i-1]) continue; 
            vector<int> ans0(3,0); 
            ans0[0] = nums[i]; 
            int t = 0 - nums[i]; 
            int l = i+1, r = nums.size()-1; 
            while(l < r) 
            { 
                if(nums[l] + nums[r] == t) 
                { 
                    ans0[1] = nums[l]; 
                    ans0[2] = nums[r]; 
					//如果下一个数和当前数相等,跳过 
                    while(l<r && nums[l+1] + nums[r] == t) l++; 
                    while(l<r && nums[l] + nums[r+1] == t) r++; 
                    ans.push_back(ans0); 
                    l++; 
                    r--; 
                }else if(nums[l] + nums[r] < t) 
                    l++; 
                else 
                    r--; 
            } 
        } 
        vector<vector<int>> ans(s.begin(), s.end()); 
        return ans; 
    } 
}; 

结果

不使用set的做法速度更快一些。

311 / 311 test cases passed.
Status: Accepted
Runtime: 49 ms

311 / 311 test cases passed.
Status: Accepted
Runtime: 109 ms


标签:加密算法
声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

我的关注

全民解析

搜索
关注我们