LeetCode16-最接近的三数之和

Source

LeetCode16-最接近的三数之和

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

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

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

一、思路

(一)三指针

先对向量进行排序,然后设置三个指针:i,j,k

  • 外层循环:遍历i
  • 内层循环:双指针求和
    判断距离可以使用绝对值,预先将最小距离设置为最大值,每次计算的三数之和与目标的距离如果小于最小距离,就将其替换。

C++代码:

class Solution {
public:
	int threeSumClosest(vector<int>& nums, int target) {
		int closest_sum, i, j, k;
		int sum, distance, distance_min = INT32_MAX;
		sort(nums.begin(), nums.end());
	
		for (i = 0; i < nums.size() - 2; i++) {
			j = i + 1;
			k = nums.size() - 1;
			while (j < k) {
				sum = nums[i] + nums[j] + nums[k];
				distance = abs(sum - target);
				if (distance == 0)
					return target;

				if (distance_min > distance) {
					distance_min = distance;
					closest_sum = sum;
				}

				if (sum > target)
					k--;
				else
					j++;
			}
		}
		return closest_sum;
	}
};

执行效率:
在这里插入图片描述