Joyce' Blog
0%

3Sum

发表于

题目描述

给一组整数，求出所有和为零的三元组。

解决方案

暂时只想到了遍历，还没有想到复杂度更低的方法

  • vector<vector> res; 注意赋值时，要使用push_back()，而不是=

  • 注意去重！

  • 最开始使用了三层循环，结果时间超限，所以将最内层循环换成了二分查找

代码

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
vector<vector<int>> threeSum(vector<int>& nums) {
	//为了去重，将数字排序，与前面重复的数字就不要再向后搜索
	sort(nums.begin(), nums.end());

	int size = nums.size();
	vector<vector<int>> res;
	int usedi = 0; int usedj = 0; 
	bool flag = true;//有三个以上的0时，只加入一次
	for (int i = 0; i < size - 2; ++i)
	{		
		for (int j = i + 1; j < size - 1; ++j)
		{			
			int t = 0 - nums[i] - nums[j];
			if (t >= 0)
			{//既然已经经过排序，那么要找的第三个数一定是个非负数
			 //复杂度过高，将内层的遍历改成二分查找
				int left = j + 1; int right = size - 1;
				while (left <= right)
				{
					int mid = (left + right) / 2;
					if (nums[mid] < t)
					{
						left = mid+1;
					}
					else if (nums[mid] > t)
					{
						right = mid-1;
					}
					else
					{
						vector<int> y;
						y.push_back(nums[i]);
						y.push_back(nums[j]);
						y.push_back(t);
						res.push_back(y);
						break;
					}
				}
			}
			usedj = nums[j];
			while ( j < size - 2 && usedj == nums[j+1])
				++j;
		}	
		usedi = nums[i];
		while ( i < size - 3 && usedi == nums[i+1])
			++i;//与前面重复的数字就不要再向后搜索
	}
	return res;
}

找到另外一种思路：不需要三层，两层就够了，外层思路不变，在内层，从两端向中间移动。

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
vector<vector<int>> threeSum2(vector<int>& nums) {
	//为了去重，将数字排序，与前面重复的数字就不要再向后搜索
	sort(nums.begin(), nums.end());

	int size = nums.size();
	vector<vector<int>> res;
	int usedi = 0; int usedj = 0;
	bool flag = true;//有三个以上的0时，只加入一次
	for (int i = 0; i < size - 2; ++i)
	{
		int j = i + 1; int k = size - 1;

		while (j < k)
		{
			int t = nums[i] + nums[j] + nums[k];
			if (t == 0)
			{
				vector<int> y;
				y.push_back(nums[i]);
				y.push_back(nums[j]);
				y.push_back(nums[k]);
				res.push_back(y);
				while (j < size - 2 && nums[j] == nums[j + 1]) ++j;
				while (k > 0 && nums[k] == nums[k - 1]) --k;
				++j;
				--k;
				continue;
			}
			else if (t > 0)
				--k;
			else
				++j;
		}
		usedi = nums[i];
		while (i < size - 3 && usedi == nums[i + 1])
			++i;//与前面重复的数字就不要再向后搜索
	}
	return res;
}