Given an arraySofnintegers, are there elementsa,b,cinSsuch thata+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)
掌握了这样的题的要诀就好办:
1 排序
2 前面的两个小数和后面的一个大数相加比较,如果小于0,那么前面的数往前进,增大; 如果大于0,那么后面的数往前进,减小。
3 前面的数和后面的数相遇,本次循环结束。
如本程序,第一个i可以看做是定标,j是前面的数,k是后面的数。
还有注意的就是:记得越过重复的数,以避免答案重复。当然也可以使用额外的数据结果,如set来作为容器,不允许重复数据的,或者最后使用unique处理掉重复元素。
最好还是踏踏实实用实例走一走,就可以发现很多原来无法发现的问题。用的实例最好包括特例的实例,例如空,重复,边界重复等。
可以参考leetcode:http://leetcode.com/2010/04/finding-all-unique-triplets-that-sums.html
下面带测试完整程序,方便一下初学者
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class Solution {
public:
vector<vector<int> > threeSum(vector<int> &num)
{
sort(num.begin(), num.end());
int i=0, j=0, k=num.size()-1;
int num1 = 0;
vector<int> t(3);
vector<vector<int> > vt;
for (; i < k-1; )
{
num1 = 0-num[i];
t[0] = num[i];
for (j = i+1, k=num.size()-1; j < k;)
{
if (num[j] + num[k] == num1)
{
t[1] = num[j++];
t[2] = num[k--];
vt.push_back(t);
while (j<k && num[j] == num[j-1])
{
j++;
}
while (j<k && num[k] == num[k+1])
{
k--;
}
}
else if (num[j] + num[k] < num1)
{
j++;
}
else
{
k--;
}
}
i++;
while (i<k-1 && num[i] == num[i-1])
{
i++;
}
}//for(; i<k-1; i++)
return vt;
}
};
int main()
{
vector<vector<int> > vt;
int a[] = {-2,13,-5,-4,-7,8,0,-9,6,7,0,-4,2,1,-2,4};
int len = sizeof(a)/sizeof(int);
vector<int> t(a, a+len);
Solution solu;
vt = solu.threeSum(t);
for (auto x:vt)
{
cout<<"(";
for (auto y:x)
cout<<y<<"\t";
cout<<")"<<endl;
}
cout<<endl;
system("pause");
return 0;
}
2014-1-24 update
本题使用set容器防止重复会超时的,更新一下,看起来简洁点,思想是和上面的一样的:
vector<vector<int> > threeSum(vector<int> &num)
{
vector<int> tmp(3);
vector<vector<int> > rs;
sort(num.begin(), num.end());
for (int i = 0; i < num.size(); i++)
{
for (int j = i+1, k = num.size()-1; j < k; )
{
if (num[i]+num[j]+num[k] < 0) j++;
else if (num[i]+num[j]+num[k] >0) k--;
else
{
tmp[0] = num[i];
tmp[1] = num[j];
tmp[2] = num[k];
rs.push_back(tmp);
j++, k--;
while (j<k && num[j] == num[j-1]) j++;
while (j<k && num[k] == num[k+1]) k--;
}
}
while (i<num.size() && num[i] == num[i+1]) i++;
}
return rs;
}
分享到:
相关推荐
双指针算法,python数组双指针算法求和问题LeetCode2sum3sum4sum含代码
python python_leetcode面试题解之三数之和_3sum
文档python数组双指针算法求和问题LeetCode2sum3sum4sum含代码提取方式是百度网盘分享地址
Leetcode two sum java 解法
(C++)LeetCode刷题题解答案
c++ c++_c++编程基础之leetcode题解第15题三数之和
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2)...
判断字符串是否为回文数,leetcode原题,使用多种方法
大佬的leetcode刷题笔记(c++版本)
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101.zip
LeetCode 101:和你一起你轻松刷题(C++)
python python_leetcode面试题解之两数之和TwoSum
oj.leetcode题解, 2sum, 运用hashtable解决这到问题,时间复杂度O(N)
leetcode上C++版本资源,完整的C++代码,包括数据结构、算法等。
15 | [3 Sum](https://leetcode.com/problems/3sum/) | [C++](./C++/3sum.cpp) [Python](./Python/3sum.py) | _O(n^2)_ | _O(1)_ | Medium || Two Pointers 16 | [3 Sum Closest]...
刷leetcode的记录,C++和Python两种语言的实现.zip刷leetcode的记录,C++和Python两种语言的实现.zip刷leetcode的记录,C++和Python两种语言的实现.zip刷leetcode的记录,C++和Python两种语言的实现.zip刷leetcode的...
Sum vii. Find Minimum in Rotated Sorted Array viii. Largest Rectangle in Histogram ix. Maximal Rectangle x. Palindrome Number xi. Search a 2D Matrix xii. Search for a Range xiii. Search Insert ...
c++ c++_c++编程基础之leetcode题解第18题四数之和
c++ c++_c++编程基础之leetcode题解第1题两数之和
【leetcode】斐波那契数 c++(csdn)————程序