題目

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. 最接近的三数之和（双指针）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。