leetcode 16. 3Sum Closest

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

문제설명

• n개의 갯수를 가진 정수 배열 nums와 정수 target 제공
• nums에서 3개의 숫자 합이 target과 가장 가까울 때 이 때의 3개 숫잡 합을 구하시오

예

• Input: nums = [-1,2,1,-4], target = 1
• Output: 2

문제접근

• 못품, 그래서 정답지를 분석
• nums을 순회
• n-2까지만 순회, 왜냐면 순회값을 기준으로 최소, 최대를 의미하는 두 index를 가짐
• 그래서 이 순회값과 두 index를 통해 계산된 값이 target보다 작으면 최소 index를 올려주고 target보다 크면 최대 index를 줄여줌으로서 target 값에 근사하도록 함

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:


    int threeSumClosest(vector<int>& nums, int target) {
        int rtn;

        sort(nums.begin(), nums.end());

        int nums_size = nums.size();
        int left_idx = 0;
        int right_idx = nums_size;
        int cur;

        rtn = nums[0] + nums[1] + nums[2];

		// n-2개 순회, 왜? left, right는 n보다 앞
        for(int i=0; i< nums_size-2; i++){
            right_idx = nums_size-1;
            left_idx = i+1;

            while(left_idx < right_idx){
                cur = nums[i] + nums[left_idx] + nums[right_idx];
                if(abs(cur - target) < abs(rtn - target)){
                	// 현재 계산된 값이 정답에 가까우면 바꿔줌
                    rtn = cur;
                }

                if(cur < target) left_idx++;
                else if(cur > target) right_idx--;
                else return rtn;
            }
        }

        return rtn;
    }
};

int main() {
    Solution sol;

    //Input: nums = [-1,2,1,-4], target = 1
    //Output: 2

    vector<int> nums{-1,2,1,-4};
    int target = 1;

    auto ans = sol.threeSumClosest(nums, target);
    cout << ans << endl;
    return 0;
}