[JAVA] LeetCode - 3Sum Closest - 16

문제내용

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

3Sum Closest - LeetCode

Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.

Return the sum of the three integers.

You may assume that each input would have exactly one solution.

 

Example 1:

Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Example 2:

Input: nums = [0,0,0], target = 1
Output: 0

 

Constraints:

• 3 <= nums.length <= 1000
• -1000 <= nums[i] <= 1000
• -104 <= target <= 104

---

문제 접근 방법

만약 15번 문제를 풀었다면 쉽게 풀수 있는 문제다. 15번 문제는 풀어놓고 아직 포팅안했는데 이후에 할예정!

아무튼 기본적인 로직을 생각보면 완전탐색으로 풀려고하면 배열이 길이가 최대 1000이라서 최대 1,000,000,000 탐색해야돼서 무조건 시간초과가 난다.

 

이를 줄일수 있는 방법은 최대 1,000,000으로 푸는 방법인데 투포인터를 쓰면된다.

투포인터는 특정값인 target을 찾는 알고리즘으로 start, end 두개의 인덱스를 가지고, 정렬된 arr 배열에서

arr[start] + arr[end] > target 이라면 end--를 해주고

arr[start] + arr[end] < target 이라면 start++을 해주면 된다.

 

여기서도 마찬가지다. 물론 항이 3개이긴 하지만 위를 응용한다면 2개의 포인터 + 하나는 내가 미리 정해놓은값 으로 활용할수 있다. 한마디로 '내가 미리 정해놓은 값' + nums[start] + nums[end] 를 target과 비교해서 target과 차이가 가장 많이 안나는 값이 정답이된다.

 

여기서 '내가 미리 정해놓은 값'은 for문을 통해 앞에 요소부터 하나씩 선택하게된다.

그래서 투포인터까지 해가지고 결론적으로 O(N^2)의 시간복잡도가 들게된다.

 

---

풀이

import java.util.Arrays;

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

---

마치며

투포인터를 활용한 문제로 말했다시피 15번 문제가 더어렵고 16번을 푼뒤에 15번 문제를 푸는것을 추천한다.