leetcode 16

最接近的三数之和

Posted by Static on June 24, 2020

题目链接:https://leetcode-cn.com/problems/3sum-closest/

题目描述


分析

1. 循环

左、右指针,详细看代码


代码实现

public enum Q16 {
    instance;
    public int threeSumClosest(int[] nums, int target) {
        // 排序
        Arrays.sort(nums);
        int size=nums.length;
        int t=nums[0]+nums[1]+nums[2];
        for(int i=0;i<size;i++){
            int l=i+1,r=size-1;
            while (l<r){
                int s=nums[i]+nums[l]+nums[r];
                // 比较绝对值
                if(abs(s-target)<abs(t-target)){
                    // 交换
                    t=s;
                }
                // 目标值大右移
                if(target>s){
                    l++;
                // 目标值小左移
                }else if(target<s){
                    r--;
                // 相等直接返回
                }else {
                    return t;
                }
            }
        }
        return t;
    }

    private int abs(int n){
        return n>=0?n:-n;
    }

    public static void main(String[] args) {
        // assert 2
        System.out.println(Q16.instance.threeSumClosest(new int[]{-1,2,1,-4},1));
    }
}