[LeetCode] 16. 3Sum Closest

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

3Sum Closest - LeetCode

3Sum Closest

 

 

3Sum 문제에서 조금 업그레이드 된 문제다.

더했을때 target이 되는걸 찾아내는게 아닌, target과 가장 가까운 수를 찾아내는 것이다.

풀이방법은 3Sum과 같다.

다만 이번엔 포인터를 움직일때마다 target과 얼마나 가까운지 저장을 해주면 된다.

 

전체 풀이 코드

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