首页 > 代码库 > Leetcode--3Sum
Leetcode--3Sum
Problem Description:
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)分析:题目要求把所有可能的集合都找出来,因此想到的就是首先将数组排序,然后利用两重循环依次选出两个数字a和b,然后在剩下的数字中查找是否存在c,具体实现用到了upper_bound函数找到比当前数大的第一个数,去掉重复循环的情况,然后用find函数查找c是否存在,存在则将三个数记录下来。具体代码如下:
class Solution { public: vector<vector<int> > threeSum(vector<int> &num) { vector<vector<int> > results; if(num.size()<3) return results; vector<int> subset; sort(num.begin(),num.end()); vector<int>::iterator p=num.begin(),q,flag; while(p<(num.end()-2)) { q=p+1; while(q<num.end()-1) { int tag=0-*p-*q; if(find(q+1,num.end(),tag)!=num.end()) { flag=find(q+1,num.end(),tag); subset.push_back(*p); subset.push_back(*q); subset.push_back(*flag); results.push_back(subset); } subset.clear(); q=upper_bound(q,num.end()-1,*q); } p=upper_bound(p,num.end()-2,*p); } return results; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。