Joyce' Blog
0%

3sum-closest

发表于

题目描述

给一组数，和一个数字target，找出三个数字，使这三个数字的和最接近target。这个问题，其实和3Sum相同，也难怪这个题的通过率会是上一题的二倍了。

解决方案

要注意赋给res的初值。并且我认为不用去除重重复搜索的操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int threeSumClosest(vector<int>& nums, int target) {
	sort(nums.begin(),nums.end());
	int size = nums.size();
	int res = nums[0] + nums[1] + nums[2];
	for (int i = 0; i < size - 2; i++)
	{
		int j = i + 1; int k = size - 1;
		while (j < k)
		{
			int sum = nums[i] + nums[j] + nums[k];
			if (abs(sum-target) < abs(res-target))
				res = sum;
			if (sum < target)
				++j;
			else if (sum > target)
				--k;
			else
				return target;
		}
	}
	return res;
}