leetcode(16)最接近的三数之和

骑猪看日落 2021-11-01 08:30 352阅读 0赞

最接近的三数之和

解题思路：排序+双指针

class Solution {
        public int threeSumClosest(int[] nums, int target) {
            int len = nums.length;
            Arrays.sort(nums);
            int l = 0;
            int r = 0;
            int min = Math.abs(nums[0]+nums[1]+nums[2]-target);
            int sum = nums[0]+nums[1]+nums[2];
            int temp = 0;
            int temp2 = 0;
            int flag =0;
            for(int i=0;i<len-2;i++){
                l=i+1;
                r=len-1;
                flag = 0;
                while(l<r){
                    temp = nums[i]+nums[r]+nums[l];
                    if(temp<target){
                        if(flag==-1){
                            if(Math.abs(temp-target)<min) {
                                min = Math.abs(temp-target);
                                sum = temp;
                            }
                            temp2 = nums[i]+nums[r+1]+nums[l];
                            if(Math.abs(temp2-target)<min){
                                min = Math.abs(temp2-target);
                                sum = temp2;
                            }
                        }
                        flag=1;
                        while(l<r&&nums[l+1]==nums[l]){
                            l++;
                        }
                        l++;
                    }else if(temp>target){
                        if(flag==1){
                            if(Math.abs(temp-target)<min) {
                                min = Math.abs(temp-target);
                                sum = temp;
                            }
                            temp2 = nums[i]+nums[r]+nums[l-1];
                            if(Math.abs(temp2-target)<min){
                                min = Math.abs(temp2-target);
                                sum = temp2;
                            }
                        }
                        flag=-1;
                        while(l<r&&nums[r-1]==nums[r]){
                            r--;
                        }
                        r--;
                    }else{
                        return temp;            
                    }
                }
                if(flag==1){
                    temp = nums[i]+nums[r]+nums[l-1];
                    if(Math.abs(temp-target)<min){
                        min = Math.abs(temp-target);
                        sum = temp;
                    }
                }else{
                    temp = nums[i]+nums[r+1]+nums[l];
                    if(Math.abs(temp-target)<min){
                        min = Math.abs(temp-target);
                        sum = temp;
                    }
                }
            }
            return sum;
        }
    }

转载于:https://www.cnblogs.com/erdanyang/p/11151640.html