首页 > 代码库 > 【LeetCode】3Sum
【LeetCode】3Sum
3Sum
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:
- Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
- 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)
这题最naive的做法是三重循环遍历,但是O(n^3)的复杂度肯定是TLE的,即使进行优化也无效。
关键点在于将数组排序之后,就可以省掉很多重复操作。
利用“后面的元素>=前面的元素"这一点,将复杂度降为O(n^2)。
class Solution{public: vector<vector<int> > threeSum(vector<int> &num) { vector<vector<int> > result; sort(num.begin(), num.end()); for(vector<int>::size_type st1 = 0; st1 < num.size(); st1 ++) { //如果num[st1]==num[st1-1],那么在num[st1-1]为首的情况下已经cover以num[st1]为首的所有情况 if(st1>0 && num[st1]==num[st1-1]) continue; vector<int>::size_type st2 = st1+1; vector<int>::size_type st3 = num.size()-1; while(st2 < st3) { //如果num[st3]==num[st3+1],那么在num[st3+1]为尾的情况下已经cover以num[st3]为尾的所有情况 if(st3<num.size()-1 && num[st3]==num[st3+1]) { st3--; continue; } int sum = num[st1]+num[st2]+num[st3]; if(sum < 0) st2++; else if(sum > 0) st3--; else { vector<int> v; v.push_back(num[st1]); v.push_back(num[st2]); v.push_back(num[st3]); result.push_back(v); st2++; st3--; } } } return result; }};
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。