leetcode #16 最接近的三数之和 | 刷题之路第一站——数组类相关问题

题号 16

题目描述

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

示例:

例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.

与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

链接：leetcode #16 最接近的三数之和

解题思路【双指针】：

参考 leetcode #15 三数之和 中【双指针】的解法。
1 - 对给定nums数组进行排序；
2 - 设立两个变量
result 存放最接近 target 的三数之和
sum 存放当前循环中的三数之和
3 - 对于nums数组中的每一个元素nums[i]
首先设定两个指针：L = i + 1, R = nums.size() -1
当 L < R 时，进行如下循环：
（1）计算 sum = nums[i] + nums[L] + nums[R]，如果 sum 值与 target 相等，则直接返回 sum 值；
（2）否则：判断 result 和 sum 哪个更接近 target，如果 sum 更接近，则将 sum 赋值给 result；
（3）如果 sum < target，则需要将 sum 增大使得其更接近 target，因此将 L 后移；
（4）如果 sum > target，则需要将 sum 减小使得其更接近 target，因此将 R 后移。
4 - 最后返回 result 值。
时间复杂度分析：
在最坏情况下，
i = 0 时，L 和 R 共移动 n-1 次；
i = 1 时，L 和 R 共移动 n-2 次；
i = 2 时，L 和 R 共移动 n-3 次；
……
i = n-3 时，L 和 R 共移动 2 次；
所以，T(n) = 2 + 3 + …… + (n-1) = (n^2-n-2) / 2
在最坏情况下，时间复杂度为：O(n^2)
显然最好情况下，时间复杂度为：O(1)

代码实现：

class Solution {
public:
	int threeSumClosest(vector<int>& nums, int target) {
		int result = nums[0] + nums[1] + nums[nums.size() - 1], sum;    //result存放截止到现在最接近target的和值，sum存放当前循环中的三数之和
		sort(nums.begin(), nums.end());    //对给定数组进行排序
		for (int i = 0; i < nums.size(); i++)    //对于数组中每个元素都进行如下的循环
		{
			int L = i + 1, R = nums.size() - 1;     //设定两个指针L和R
			while (L < R)
			{
				sum = nums[i] + nums[L] + nums[R];
				if (sum == target)    //如果当前三数之和等于target，则直接返回当前sum值，问题解决
					return sum;
				int differ1 = abs(target - sum);    //否则就计算sum和result哪个更接近target
				int differ2 = abs(target - result);
				if (differ1 < differ2)
					result = sum;
				if (sum < target)    //如果当前sum值小于target，则将L右移一个元素
					L++;
				else if (sum > target)    //如果当前sum值大于target，则将R左移一个元素
					R--;
			}
		}
		return result;
	}
};

代码改进：
因为我们在一开始就对给定的数组进行了排序，因此对于某个元素而言，如果它和前一个元素相同，则没必要再对该元素进行接下来的循环和判断，因为所有可能三元组之和都在前一个元素循环时进行了计算。所以我们在for循环一开始可以增加一个判断该元素是否与前一个元素相等，若相同则直接结束此次循环，进入下次循环，这样可以节省时间。

class Solution {
public:
	int threeSumClosest(vector<int>& nums, int target) {
		int result = nums[0] + nums[1] + nums[nums.size() - 1];
		sort(nums.begin(), nums.end());
		for (int i = 0; i < nums.size(); i++)
		{
			if (i > 0 && nums[i] == nums[i - 1]) continue;    //此处为增加的判断当前元素是否与其前一个元素相同
			int L = i + 1, R = nums.size() - 1;
			while (L < R)
			{
				int sum = nums[i] + nums[L] + nums[R];
				if (sum == target)
					return sum;
				if (abs(target - sum) < abs(target - result))   
					result = sum;
				if (sum < target)
					L++;
				else if (sum > target)
					R--;
			}
		}
		return result;
	}
};