3Sum Closest(最接近target的三个数字的和)leetcode16

谁践踏了优雅 2022-05-24 08:23 161阅读 0赞

Given an array `nums` of *n* integers and an integer `target`, find three integers in `nums` such that the sum is closest to `target`. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Example:

Given array nums = [-1, 2, 1, -4], and target = 1.
    
    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

code1：（暴力破解）

public static int threeSumClosest(int[] nums, int target) {
        	int closest=Integer.MAX_VALUE;
        	int resultSum=0;
            Arrays.sort(nums);
            for(int i=0;i<nums.length;i++)
             for(int j=i+1;j<nums.length;j++)
                 for(int k=j+1;k<nums.length;k++)
                     if(Math.abs(target-nums[i]-nums[j]-nums[k])<closest) {
                         closest=Math.abs(target-nums[i]-nums[j]-nums[k]);
                         resultSum=nums[i]+nums[j]+nums[k];
                         //System.out.println(closest);
                        }
            return resultSum;
    }

code2：（优化后的）

public static int threeSumClosest(int[] nums, int target) {
            Arrays.sort(nums);
            int result=nums[0]+nums[1]+nums[2];
            for(int i=0;i<nums.length-2;){
                int front=i+1;
                int last=nums.length-1;
                while(front<last){
                    int sum=nums[i]+nums[front]+nums[last];
                    if(sum==target) return sum;
                    if(Math.abs(sum-target)<Math.abs(target-result))
                        result=sum;
                    if(sum>target){
                        last--;
                         while(last>front&&nums[last]==nums[last+1]) last--;
                    }
                    if(sum<target){
                        front++;
                        while(front<last&&nums[front]==nums[front-1]) front++;
                    }
                    
                   
                }
                i++;
                while(i<nums.length&&nums[i]==nums[i-1])
                    i++;
            }
            return result;
        }
    }