[leetcode] 16. 3Sum Closest

문제

Given an array nums of n integers 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.

 

풀이

3Sum 문제와 기본적으로 알고리즘은 동일하다.

반복하는 동안 해야할 일만 조금 다르다.

현재의 합이 지금까지 찾은 답보다 target에 가까운지 체크하고, 가까우면 갱신해주는 것 뿐이다.

 

Time Complexity : $O(n^2)$

 

코드

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