[array] 3sum closest

✅ Problem

https://leetcode.com/problems/3sum-closest/description/

 

✅ Approach & Solution

방식) 정렬 후 투 포인터 사용

• 3개를 찾아야 할 때 : 1개는 고정해두고 나머지 2개를 찾자
• 나머지 2개 찾을 때 투 포인터 사용
  • 정렬 필수 (배열의 인덱스 값 활용하지 않기 때문에 정렬 가능)

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        int result = 0; // 반환할 세 수의 합

        int minDiff = Integer.MAX_VALUE; // target과 세 수의 합의 최소 차이

        int left, right, sum;

        Arrays.sort(nums);

        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i-1]) { // 중복값은 skip
                continue;
            }

            // 나머지 2개 찾기
            left = i + 1;
            right = nums.length - 1;

            while (left < right) {
                sum = nums[i] + nums[left] + nums[right];

                if (sum > target) {
                    if (sum - target < minDiff) {
                        minDiff = sum - target;
                        result = sum;
                    }

                    // right 포인터 조정 (중복 값 나오지 않을 때까지)
                    while (left < right && nums[right] == nums[right - 1]) {
                        right -= 1;
                    }
                    right -= 1;
                } else if (sum < target) {
                    if (target - sum < minDiff) {
                        minDiff = target - sum;
                        result = sum;
                    }

                    // left 포인터 조정 (중복 값 나오지 않을 때까지)
                    while (left < right && nums[left] == nums[left + 1]) {
                        left += 1;
                    }
                    left += 1;
                } else { // sum == target
                    return sum;
                }
            }
        }

        return result;
    }
}