数据结构-三数之和为零

发表于   |   分类于   |     |   阅读次数

题意:给定一个排序数组（小->大），取数组中的三个元素a,b,c;满足a+b+c=0,a<=b<=c;
举例：A=[-1,-1,-1,0,1,2,3],result=[-1,-1,2],[-1,0,1];
思路：双指针思想+枚举。
当枚举数组的第一个元素时，设置两个指针left,right分别指向数组的第一元素和最后一个元素。
当a[left]+a[right] > (-a[i]),right– (0<=i0时，直接结束，因为数组是递增的，绝不会再出现a+b+c=0的情况；
（2）去掉重复判断，当a[i-1]==a[i],可以直接跳过第i次循环

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	int n;
	while(cin>>n)
	{
		if(n == 0) continue;
		vector<int> dp(n,0);
		for (int i = 0; i < n; ++i)
		{
			cin>>dp[i];
		}
		sort(dp.begin(),dp.end());
		//双指针
		for (int i = 0; i < n; ++i)
		{
			if(dp[i] >0) break;
			if(i>0 && dp[i-1]==dp[i])
				continue;
			int a = dp[i];
			int left = i+1;
			int right = n-1;
			while(left < right)
			{
				int b = dp[left];
				int c = dp[right];
				if(-a < b + c)
					right--;
				else if(-a > b + c)
					left++;
				else 
				{
					cout<<a<<" "<<b<<" "<<c<<endl;
					do
					{
						left++;
					} while (left < right && dp[left-1] == dp[left]);
					do
					{
						right--;
					} while (left < right && dp[right+1] == dp[right]); 
				}
			}
		}
	}
}