首页 > 代码库 > LeetCode-3Sum
LeetCode-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.
思路分析:
- 先将数组按增序排序.
- 遍历数组,设置3个指针i,j,k，先确定i的位置,记b=a[j]=a[i+1],c=a[k]=a[n-1].
- 如果a+b+c>0,则k--,若a+b+c<0，则j++,若a+b+c==0,则保存下来.
- 同时要注意，题目要求not contain duplicate,所以a=a[i]时要判断是否和a[i-1]相等，若相等,则此问题已解决过，同理也要判断b和c相等的情况.
代码:
#include <iostream>#include <vector>#include <string>vector<vector<int> > threeSum(vector<int> &num){ vector<vector<int> > ret; if(num.empty()) return ret; int size=num.size(); sort(num.begin(),num.end()); for(vector<int>::const_iterator it=num.begin();it!=num.end();it++){ if(it!=nu.begin() && *it==*(it-1)) continue; vector<int>::const_iterator front=it+1; vector<int>::const_iterator back=num.end()-1; while(front<back){ int sum=*it+*front+*back; if(sum>0){ back--; } else if(sum<0){ front++; } else if(front!=it+1 && *front==*(front-1)){ front++; } else if(back!=num.end() && *back==*(back+1)){ back--; } else{ vector<int> rsesult; result.push_back(*it); result.push_back(*front); result.push_back(*back); ret.push_back(result); front++; back--; } } } return ret;}
LeetCode-3Sum
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。