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

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;
    }
}