16. 3Sum Closest

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

3Sum Closest - LeetCode

난이도 : medium

문제 

target 가 가까운 3 정수의 합을 구하여라

INPUT 이 1000 이라서 삼중 반복문으로도 풀린다. 하지만 그이상에 INPUT 이 들어온다면 투포인터로 접근해야 한다.

 

코드

브루스 포스 풀이

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {

        int sol = 0;
        int dist = 987654321;
        for(int i = 0 ; i < nums.size(); ++i) {
            for(int j = i+1; j < nums.size(); ++j) {
                for(int k = j + 1; k < nums.size(); ++k) {
                    int cand = nums[i] + nums[j] + nums[k];
                    
                    if(abs(dist - target) > abs(target - cand))
                    {
                        dist = cand;
                        sol = cand;
                    }
                }
            }
        }
        return sol;
    }
};

 

투포인터 풀이

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        
        sort(nums.begin(), nums.end());
        
        int ans = nums[0] + nums[1] + nums[2];
        for(int i = 0; i < nums.size()-2; ++i) {
            
            int left = i + 1;
            int right = nums.size() - 1;
            
            while(left < right) {
                int cand = nums[i] + nums[left] + nums[right];
                
                if(abs(target - cand) < abs(target - ans)) {
                    ans = cand;
                }                
                
                if (cand == target) {
                    break;
                }
                
                if (cand < target) {
                    left++;
                }
                else {
                    right--;
                }
            }
        }
        
        return ans;
    }
};