Leetcode 16) 3Sum Closest

24 Sep 2021 in Algorithms

My Answer

• 푸러따아아ㅏ~~~ 실력이 늘고있는거같아서 기쁘다아아아
• recursive하게 내려게 해서! 다만 target이 음수일 수도 있다는 것을 캐치를 못해서 맨 처음 submit은 틀림

class Solution {
    int globalMin;
    public int threeSumClosest(int[] nums, int target) {
        globalMin=Integer.MAX_VALUE;
        for(int i =0;i<nums.length;i++){
            helper(target-nums[i], 2, nums ,i+1);
        }
        return target-globalMin;
    }
    
    public void helper(int targetDist, int cnt, int[] nums, int start){
        if(cnt==0){
            if(Math.abs(globalMin)>Math.abs(targetDist)){
                globalMin=targetDist;
            }
            return;
        }
        cnt--;
        //i 부터 시작해야지 중복이 생기지 않아서, time complexity가 줄어든다.
        for(int i =start; i<nums.length;i++){
                helper(targetDist-nums[i], cnt, nums ,i+1);
            
               
        }
    }
}

Other Answer

• pointer로 푼 것 이해하기
• 정렬 먼저해서 pointer로 풀 수 있다!! 두 포인터를 맨 끝값으로 잡고,

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int closest = nums[0] + nums[1] + nums[2];
        
        for (int i = 0; i < nums.length - 1 && closest != target; i++) {
            int currClosest = twoSumClosest(nums, i, target);
            if (Math.abs(target - currClosest) < Math.abs(target - closest)) closest = currClosest;
        }
        
        return closest;
    }
    
    private int twoSumClosest(int[] nums, int i, int target) {
        int closest = nums[0] + nums[1] + nums[2];
        
        int left = i + 1;
        int right = nums.length - 1;
        
        while (left < right) {
            int curr = nums[i] + nums[left] + nums[right];
            if (Math.abs(target - curr) < Math.abs(target - closest)) closest = curr;
            
            if (target - curr < 0) right--;
            else left++;
        }
        
        return closest;
    }
    
    
}