16. 3Sum Closest

Link

Solution

-> brute force -> O(n!)the factorial of n

-> two-pointer with a sorted array : O(n^2)

固定一個pointer，尋找其他可能的2個pointer

要sort過array才可以依照大小順序，進行比較聰明的找法

1,2,3,4,5,....9,10,11,12,15

i start end

當 nums[i] + nums[start] + nums[end] > target 表示值應該要在大, start ++

當 nums[i] + nums[start] + nums[end] < target 表示值應該要在小, end--

   public int threeSumClosest(int[] nums, int target) {
        int ret = nums[0] + nums[1] + nums[2];
        Arrays.sort(nums); //O(nlogn)
        
        for(int i = 0; i < nums.length - 2; i++){ //O(n^2)
            int start = i+1, end = nums.length-1;
            
            while(start < end){
                int value = nums[i] + nums[start] + nums[end];
                
                if(value == target) return value;
                
                else if(value < target){
                    start++;
                }
                else if(value > target){
                    end--;
                }
                ret = Math.abs(target - value) < Math.abs(target - ret) ? value : ret; 
            }
        }
        return ret;
    }