LeetCode: 3Sum Closest

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

 

투포인터를 활용하여 이분탐색을 해야했다.

 

먼저 정렬을 하고 양 끝 점의 투포인터 아이디어를 떠올렸으나 정렬을 안하고도 풀 수 있는 방식이 있는지에 대한 고민을했다.

 

하지만 딱히 다른 방도가 없었고 정렬을 한다음 움직이기 시작하기로 했다.

 

 

아이디어는 다음과 같다.

 

start로 반복문을 순회하면서 인덱스를 올리고

end는 배열의 끝 인덱스

mid는 start의 바로 앞에 두어서

3개의 값을 구하면서 만약 값이 target보다 크다면 end를 줄이고

작다면 mid를 올리는 방식으로 구현했다.

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int answer = nums[0] + nums[1] + nums[2];
        for (int start = 0; start < nums.length ; start++) {
            int end = nums.length - 1;
            int mid = start + 1;
            int sum = answer;
            int temp = 0;
            while(mid < end) {
                sum = nums[start] + nums[mid] + nums[end];
                if (Math.abs(sum-target) < Math.abs(answer-target)) {
                    answer =sum;
                }
                if (sum < target) {
                    mid++;
                }
                else if(sum > target) {
                    end--;
                }
                else {
                    return target;
                }
            }
        }
        return answer;
    }

}