16. 3Sum Closest

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

접근방식 1. 하나의 수를 고정하고, two pointer 방식으로 나머지 두 수의 합을 찾는다 (전수조사)

---

class Solution {
public:
    int closest(int a, int b, int t) {
        return abs(t - a) < abs(t - b) ? a : b;
    }
    
    int f(vector<int>& nums, int l, int r, int target) {
        while (l < r) {
            int m = l + (r - l)/2;
            if (nums[m] < target) l = m;
            else if (target < nums[m]) r = m;
            else return target;
            if (r == l + 1) {
                return closest(nums[l], nums[r], target);
            }
        }
        return nums[l];
    }
    
    int threeSumClosest(vector<int>& nums, int target) {
        int n = nums.size();
        int l = 0;
        int r = n - 1;
        sort(nums.begin(), nums.end());
        
        int ans = nums[0] + nums[1] + nums[2];
        while (l + 1 < r) {
            int t = target - nums[l] - nums[r];
            int m = f(nums, l + 1, r - 1, t);
            int s = nums[l] + nums[r] + m;
            ans = closest(ans, s, target);
            
            if (m < t) l++;
            else r--;
        }
        return ans;
    }
};

접근방식 2. [start, end] 두개의 수를 고정하고, binary search 등으로 나머지 하나의 값을 찾는다면?

    => 이 코드로도 통과했지만, 과연 올바른 로직일까?

 

<반례>

[s, m, e] 으로 구한 합이 target 보다 크다면, e 를 감소시키고 있다. 하지만 s 를 증가시키고 m 을 감소시켜야 할 수도 있는 것 아닌가?

[10, 15, 20, 26, 50, 60, 80, 90] / 125

 

잘못된 풀이로 통과한 것을 알 수 있다. 물론 모든 [s, e] 에 대해 처리한다면 가능한 방식이다.