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

雨点打透心脏的1/2处 2022-09-01 14:49 164阅读 0赞

## 题目 ##

[https://leetcode.com/problems/3sum-closest/][https_leetcode.com_problems_3sum-closest]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

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

时间复杂度 O(n^2)，推荐此方法。  
证明不会有元素遗漏，详见官方解答：[最接近的三数之和][Link 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

##### 方法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;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]

[https_leetcode.com_problems_3sum-closest]: https://leetcode.com/problems/3sum-closest/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/f9d0951a1d2c4196997d8e56c16a08e6.png
[Link 1]: https://leetcode-cn.com/problems/3sum-closest/solution/zui-jie-jin-de-san-shu-zhi-he-by-leetcode-solution/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20220829/37258331ff07445db5faaf8d06ed8bfc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]: /images/20220829/c472497e985c49248be51c2ebb518b61.png