[LeetCode] 16. 3Sum Closest - Two Pointer(투포인터) JAVA

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

코드설명

Two Pointer(투포인터)를 활용합니다.

 

처음에 문제를 잘못읽어서 슬라이딩 윈도우로 풀었습니다.

두번째에는, 완전탐색 방식으로 구현했습니다만, 상당히 시간이 오래걸립니다.(통과는 합니다.)

마지막으로 투포인터 방식으로 작성해보았습니다.

 

코드

정답코드3입니다. 투포인터 방식입니다.

import java.util.*;
class Solution {
    //Brute Force Time Complexity : 5^3 x 10^6
    public int threeSumClosest(int[] nums, int target) {
        int answerSum = 23001;
        Arrays.sort(nums);
        for(int i=0; i<nums.length - 2; i++){
            if(i > 0 && nums[i-1] == nums[i]) continue;
            int l1 = i;
            int l2 = i + 1;
            int r1 = nums.length - 1;

            while(l2 < r1){
                int sum = nums[l1] + nums[l2] + nums[r1];

                if(Math.abs(sum - target) < Math.abs(answerSum - target)){
                    answerSum = sum;
                    // l2 += 1; 아래 반복문과 중복되었습니다. 이 부분은 주석처리합니다.
                }

                if(sum > target){
                    r1 -= 1;
                    while(l2 < r1 && nums[r1] == nums[r1+1]) r1 -= 1;
                }else if(sum < target){
                    l2 += 1;
                    while(l2 < r1 && nums[l2] == nums[l2-1]) l2 += 1;
                }else if(sum == target){
                    return sum;
                }

            }
        }
        return answerSum;
    }
}

3중 for문을 활용한 완전탐색 방식입니다.

import java.util.*;
class Solution {
    public int threeSumClosest(int[] nums, int target) {
        int answerSum = 23001;
        for(int i=0; i<nums.length - 2; i++){
            for(int j=i+1; j<nums.length - 1; j++){
                for(int k=j+1; k<nums.length; k++){
                    int nowSum = nums[i] + nums[j] + nums[k];
                    if(Math.abs(nowSum - target) < Math.abs(answerSum - target)){
                        answerSum = nowSum;
                    }
                }
            }
        }
        
        return answerSum;
    }
}

 

처음에 잘못 작성한 코드입니다. 문제를 잘못이해해서 슬라이딩 윈도우로 처음에 잘못 풀었습니다.

import java.util.*;
class Solution {
    public int threeSumClosest(int[] nums, int target) {
        int pSum = 0;
        for(int i=0;i<2; i++){
            pSum += nums[i];
        }

        int answer = 1000 * 3 + 1;
        int answerDiff = 1000 * 3 + 1;
        for(int i=2; i<nums.length; i++){
            pSum += nums[i];
            System.out.println("target:"+target+ " pSum:"+pSum+" "+(target-pSum));
            if(Math.abs(target - pSum) < Math.abs(answerDiff)){
                answerDiff = (target - pSum);
                answer = pSum;
            }
            pSum -= nums[i - 2];
        }
        return answer;
    }
}