LeetCode 15: 3Sum

发布时间:2016-12-9 14:05:39 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"LeetCode 15: 3Sum",主要涉及到LeetCode 15: 3Sum方面的内容,对于LeetCode 15: 3Sum感兴趣的同学可以参考一下。

Difficulty: 3 Frequency: 5 Problem: 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) Solution: class Solution { public: vector<vector<int> > threeSum(vector<int> &num) { // Start typing your C/C++ solution below // DO NOT write int main() function vector<vector<int> > answer; if (num.size()<3) return answer; vector<int> triplet; sort(num.begin(), num.end()); int i_start, i_end; int sum; for (int i = 0; i<num.size()-2; ++i) { if (i>0&&num[i]==num[i-1]) continue; i_start = i+1; i_end = num.size()-1; while (i_start<i_end) { if (num[i_start]==num[i_start+1]&&num[i] + num[i_start] + num[i_start+1]==0) { triplet.clear(); triplet.push_back(num[i]); triplet.push_back(num[i_start]); triplet.push_back(num[i_start]); answer.push_back(triplet); } while (i_start<i_end&&num[i_start]==num[i_start+1]) ++i_start; if (i_start==i_end) break; if (num[i_end]==num[i_end-1]&&num[i] + num[i_end-1] + num[i_end]==0) { triplet.clear(); triplet.push_back(num[i]); triplet.push_back(num[i_end]); triplet.push_back(num[i_end]); answer.push_back(triplet); } while (i_end>i_start&&num[i_end]==num[i_end-1]) --i_end; sum = num[i] + num[i_start] + num[i_end]; if (sum==0) { triplet.clear(); triplet.push_back(num[i]); triplet.push_back(num[i_start]); triplet.push_back(num[i_end]); answer.push_back(triplet); ++i_start; } else if (sum>0) --i_end; else ++i_start; } } return answer; } }; Notes: If you know how to do 2Sum, then it is n rounds of 2Sum. I think the biggest difficulty is how to remove duplicated answers. I will consult others' code for other solution.

上一篇:hdu 4101 Ali and Baba (bfs+严密思维)
下一篇:wikioi p1079 回家

相关文章

关键词: LeetCode 15: 3Sum

相关评论