leetcode 16. 3Sum Closest | 16. 最接近的三数之和（双指针）

题目

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

题解

方法1：固定 L，双指针找 M、R

时间复杂度 O(n^2)，推荐此方法。
证明不会有元素遗漏，详见官方解答：最接近的三数之和

方法2：双指针，固定 L、R，找 M

这种方式不会导致遗漏，因为首尾已经能覆盖所有的组合。
时间复杂度O(n^2*log(n))

class Solution {public int threeSumClosest(int[] nums, int target) {Arrays.sort(nums);int dif = Integer.MAX_VALUE;for (int i = 0; i < nums.length - 2; i++) {for (int j = i + 2; j < nums.length; j++) {int t = target - nums[i] - nums[j];// 固定包含两端点元素，然后在 (L...R) 区间找到与 t 最近的数int L = i + 1;int R = j - 1;int M;while (L + 1 < R) {M = (L + R) / 2;if (nums[M] == t) return target;else if (nums[M] < t) L = M;else R = M;}if (Math.abs(nums[i] + nums[j] + nums[L] - target) < Math.abs(dif))dif = nums[i] + nums[j] + nums[L] - target;if (Math.abs(nums[i] + nums[j] + nums[R] - target) < Math.abs(dif))dif = nums[i] + nums[j] + nums[R] - target; // nums[i] + nums[j] + nums[R] = target + dif}}return target + dif;} }

总结

以上是生活随笔为你收集整理的leetcode 16. 3Sum Closest | 16. 最接近的三数之和（双指针）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。