C++LeetCode 구현(16.최근 3 수의 합)

[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.
Example:
Given array nums = [-1, 2, 1, -4], and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
이 문 제 는 우리 로 하여 금 주어진 값 에 가장 가 까 운 3 수의 합 을 구 하 게 하 는 것 은 이전 문제 이다.  3Sum  이 를 바탕 으로 약간의 난이 도 를 추 가 했 습 니 다.그러면 이 문 제 는 주어진 값 에 가장 가 까 운 값 으로 돌아 가게 합 니 다.즉,현재 3 수 와 주어진 값 사이 의 차 이 를 최소 화 하려 면 변수 diff 를 정의 하여 차 이 를 기록 하 는 절대적 인 값 을 정의 해 야 합 니 다.그 다음 에 먼저 배열 순 서 를 정 한 다음 에 배열 을 옮 겨 다 니 기 시작 해 야 합 니 다.생각 은 그 3 수의 합 과 비슷 합 니 다.모두 한 개의 수 를 먼저 정 한 다음 에 두 개의 포인터 left 와 right 로 미 끄 러 지 며 다른 두 개의 수 를 찾 습 니 다.두 개의 수 를 확정 할 때마다 이 세 수의 합 을 구 한 다음 에 주어진 값 과 의 차 이 를 계산 하 는 절대 값 은 new Diff 에 존재 합 니 다.그리고 diff 와 비교 하여 diff 와 결과 closest 를 업데이트 하면 됩 니 다.코드 는 다음 과 같 습 니 다.
해법 1:

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

우 리 는 조금 더 최적화 할 수 있 습 니 다.매번 판단 할 때마다 nums[i]*3>target 일 때 closest 와 nums[i]+nums[i+1]+nums[i+2]의 값 을 직접 비교 할 수 있 습 니 다.작은 것 으로 돌아 갈 수 있 습 니 다.배열 이 이미 순 서 를 배 정 했 기 때문에 뒤의 숫자 는 점점 커 질 뿐 뒤로 비교 할 필요 가 없습니다.코드 는 다음 과 같 습 니 다.
해법 2:

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int closest = nums[0] + nums[1] + nums[2];
        int diff = abs(closest - target);
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size() - 2; ++i) {
            if (nums[i] * 3 > target) return min(closest, nums[i] + nums[i + 1] + nums[i + 2]);
            int left = i + 1, right = nums.size() - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                int newDiff = abs(sum - target);
                if (diff > newDiff) {
                    diff = newDiff;
                    closest = sum;
                }
                if (sum < target) ++left;
                else --right;
            }
        }
        return closest;
    }
};

C++구현 LeetCode(16.최근 3 수의 합)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++구현 최근 3 수의 합 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 많은 응원 부 탁 드 리 겠 습 니 다!