欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode 16. 最接近的三数之和

程序员文章站 2022-06-06 10:32:13
...

题目描述

题目传送门

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

例如,给定数组 nums = [-1,2,1,-4], 和 target = 1.

与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).


思路

总体思路详见
LeetCode 15. 三数之和
的思路2;

先排序(从小到大),然后以每一个数为起始,在它的右边通过两个指针leftright去遍历。
这里可以用min_diff保存三个数之和sumtarget的差的绝对值的最小值, diff存储当前的差的绝对值;
那么,当diff <= min_diff时,说明当前三个数之和sum是目前最接近target的。 应该更新min_diff,更新clo_num(保存最靠近target的sum的值)


代码


int threeSumClosest(vector<int>& nums, int target) {
    int nums_sz = nums.size();
    int clo_num; // 最靠近target的sum的值
    int left, right;
    int sum; // 存储当前的sum
    int min_diff = 9999999999; // 存储最小的差绝对值
    int flag = 0; // 循环可以提前退出的条件为flag == 1

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

    for (int i = 0; i < nums_sz - 2; i++){
        if (flag == 1) // 如果存在sum==target的情况,则退出(在数组中找得到三个数使得它们的和等于target,也就是距离与target最近)
            break;

        left = i + 1;
        right = nums_sz - 1;

        // 当nums[i] == nums[i - 1]时,nums[i-1]与nums[i+1]--nums[nums_sz-1]的组合情况  和  nums[i]的情况一致,
        //  因此可以跳过nums[i]的循环,i>0保证i-1不会访问越界
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }


        while (left < right){
            sum = nums[i] + nums[left] + nums[right];
            int diff = abs(sum - target); // 当前的sum与target的差值
            if (diff <= min_diff){ // 当diff≤之前的最小的diff时,说明当前的sum更加靠近target,这里要有等于的情况,否则当输入为[1,1,1,1]时,进行第二次遍历的时候会有死循环

                min_diff = diff;
                clo_num = sum;

            }
            if (sum == target){ // 如果有遍历到sum与target相等的情况,则说明可以退出整个循环了
                flag = 1;
                break;
            }
            if (sum < target) { // 如果sum<target,说明nums[left]数值小了,left++
                left++;

                while (left < right && nums[left] == nums[left - 1]){ // 如果nums[left] == nums[left - 1](left变化之前),那么此时nums[left]--nums[right]这个范围得到的结果还是和nums[left-1]--nums[right]得到的一样
                    left++;
                }
            }

            if (sum > target){ // 如果sum>target,说明nums[right]数值大了,right--
                right--;

                while (left < right && nums[right] == nums[right + 1]){ // 同上
                    right--;
                }
            }
        }
    }

    return clo_num;
}

运行结果

LeetCode 16. 最接近的三数之和