🌕 16. 最接近的三数之和

难度: 🌕

问题描述

---

解法

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        // 思路：
        // 固定一条边，另两条边双指针查找
        Arrays.sort(nums);
        int len = nums.length;
        int res = nums[0] + nums[1] + nums[2];
        for(int i = 0; i < len - 2; i ++) {
            if(i > 0 && nums[i] == nums[i - 1]) {
                continue; // 去重
            }
            int first = nums[i];

            // 找到 [left, right] 区间 min & max
            int left = i + 1; // left 只能 ++
            int right = len - 1; // right 只能 --
            
            int min = nums[left] + nums[left + 1] + first;
            int max = nums[right - 1] + nums[right] + first;

            // 优化
            if(max == target || min == target) {
                return target; // 找到结果直接返回
            }
            if(max < target) {
                // max 即为最接近 target 的结果
                if(Math.abs(target - res) > Math.abs(target - max)) {
                    res = max;
                }
                continue;
            }
            if(min > target) {
                if(Math.abs(target - res) > Math.abs(target - min)) {
                    res = min;
                }
                continue;
            }

            // target ∈ (min, max) 需要进行区间查找
            while(left < right) {
                int cur = nums[left] + nums[right] + first;
                if(cur == target) {
                    return target;
                } else if(cur > target) {
                    while(left < right && nums[right - 1] == nums[right]) {
                        right --;
                    }
                    right --;
                    if(Math.abs(target - cur) < Math.abs(target - res)) {
                        res = cur;
                    } 
                } else {
                    while(left < right && nums[left + 1] == nums[left]) {
                        left ++;
                    }
                    left ++;
                    if(Math.abs(target - cur) < Math.abs(target - res)) {
                        res = cur;
                    }                  
                }
            }
        }
        return res;
    }
}

---

输出