[LeetCode] 16. 3Sum Closest 最近三数之和 All LeetCode Questions List 题

Given an arraySofnintegers, find three integers inSsuch that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

15. 3Sum 三数之和的拓展,这题是让找到和目标数最接近的数字组合,还是用3Sum的方法,只是这次要设一个变量minDif来记录最小差值的绝对值,如果当前三数的和与目标数的差的绝对值小于minDif则此组合更接近目标数,result变为此组合的和,迭代查找直到结束, 返回result。

C++:

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;
    }
};

All LeetCode Questions List 题目汇总

相关推荐