【Leetcode 刷题笔记】16. 3Sum Closest

题目

方案一：穷举法 o(n^3)

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        int len = nums.length;
        int ans = 100001;
        
        for(int i=0; i<len; i++){
            for(int j=0; j<len; j++){
                if(i == j)
                    continue;
                for(int k=0; k<len; k++){
                    if(i==k || j==k)
                        continue;
                    int sum = nums[i]+nums[j]+nums[k];
                    int diff = Math.abs(sum-target);
                    if(diff < Math.abs(ans-target))
                        ans = sum;
                }
            }
        }    
        return ans;

    }
}

方案二：3指针法 o(n^2)

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        int len = nums.length;
        int ans = nums[0]+nums[1]+nums[2];
        
        Arrays.sort(nums);
        for(int first=0; first<len-2; first++){
            int second = first+1, third = len-1;
            while(second < third){
                int sum = nums[first]+nums[second]+nums[third];
                if(sum > target)
                    third--;
                else
                    second++;
                if(Math.abs(sum-target) < Math.abs(ans-target))
                    ans = sum;
                if(ans == target)
                    return ans;;
            }
        }
            
        return ans;
    }
}