16. 最接近的三数之和

问题16 最接近的三数之和 ★★☆☆☆

https://leetcode-cn.com/problems/3sum-closest/

这个题目和问题15几乎一样，只是这里是计算最接近目标值的三元组的和是多少。从直觉上，我觉得这种最值问题给人的感觉更难。对于这个题目，解题思路和问题15是一致的，不赘述。还是想提一下的是，基于问题1 –> 问题167 –> 问题15 –> 问题16这样一个顺序层层递进下来，解题思路就显得”水到渠成“，否则，死记硬背也容易忘记。

	public int threeSumClosest(int[] nums, int target) {
		int len = nums.length;
		if (len == 0) {
			throw new RuntimeException("bad input");
		}

		Arrays.sort(nums);

		int ret = 0;
		int minDiff = Integer.MAX_VALUE;
		for (int i = 0; i < len; i++) {
			if (i > 0 && nums[i] == nums[i - 1]) {
				continue;
			}

			int j = i+1, k = len-1;
			while (j < k) {
				if (j > i + 1 && nums[j] == nums[j - 1]) {
					j++;
					continue;
				}

				int curSum = nums[i] + nums[j] + nums[k];

				int curDiff = Math.abs(curSum - target);
				if (curDiff < minDiff) {
					ret = curSum;
					minDiff = curDiff;
				}

				if (curSum > target) {
					k--;
				} else if (curSum < target) {
					j++;
				} else {
					return curSum;
				}
			}
		}

		return ret;
	}

在 LeetCode 查看