16. 3Sum Closest

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

3Sum Closest - LeetCode

 

임의의 정수(-10^3 ~ 10^3) 목록이 주어졌을 때, 3개의 숫자를 더해 주어진 목표 값과 가장 가까운 합을 구하는 문제다.

15. 3Sum

직전에 풀었던 문제(15. 3Sum)는 case를 구하는 문제였으므로 중복을 제거해 연산 수를 줄였지만, 이 문제는 동일한 숫자도 덧셈에 활용될 수 있어 중복 수는 제거하면 안되고, 목표 값과 3개의 합계가 동일할 때 로직을 종료시키는 방법으로 최적화한다.

 

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int min_diff = 9999999;
        sort(nums.begin(), nums.end());
        
        for (int i=0; i<nums.size(); ++i)
        {
            int l = i + 1;
            int r = nums.size() - 1;
            
            while (l < r)
            {
                int sum = nums[i] + nums[l] + nums[r];
                
                if (abs(target - sum) < abs(target - min_diff)) {
                    min_diff = sum;
                }
                
                if (min_diff == target) {
                    break;
                }
                
                if (sum < target) {
                    ++l;
                }
                else {
                    --r;
                }
            }
        }
        
        return min_diff;
    }
};