首页 🍒LeetCode,🐶算法

题目

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

示例:

输入:nums = [-1,2,1,-4], target = 1
输出:2
解释:与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

提示:

3 <= nums.length <= 10^3
-10^3 <= nums[i] <= 10^3
-10^4 <= target <= 10^4

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/3sum-closest
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

使用双指针,现将nums数组排序,然后i指向第一个元素依次到nums.size() - 2(防止越界)
定义left指针指向i + 1
定义right指针指向nums.size() - 1
若nums[i] + nums[left] + nums[right] < target。让left右移找到最适合的位置
反之让right左移

定义一个result = nums[0] + nums[1] + nums[2],如果后面有元素和target更接近则换成相应元素。
sum = nums[i] + nums[left] + nums[right]
if(abs(sum - target) < abs(result - target))如果此三个数之和更接近target则将resule换成这三个元素

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



文章评论