前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >好家伙,你管这破玩意叫“双指针”?

好家伙,你管这破玩意叫“双指针”?

作者头像
程序员小熊
发布2021-05-28 12:33:51
2960
发布2021-05-28 12:33:51
举报

1478 · 最接近target的值

描述

给出一个数组,在数组中找到两个数,使得它们的和最接近目标值但不超过目标值,返回它们的和。

解题思路

思考: 如果数组是已按照 升序排列 的,那么这个题目是不是就很好做?那样的话,可以定义两个分别 指向数组的第一个元素和最后一个元素的指针,将两个指针指向的元素和与目标值 target 进行比较,然后再根据比较的结果,决定移动那一个指针

但是由于题目没有 告知数组是有序的 ,所以需要先对数组进行 排序 ,然后再采用 双指针 的策略去做。

注意点

  1. 数组长度小于 2 时,不存在满足要求的结果,直接返回 -1
  2. 由于题目要求找到的两个数的和 最接近目标值但不超过目标值,因此只需要考虑找到的两个数的和 小于等于目标值 即可,不需要考虑大于的情况。
  3. 定义变量 diff 用于保存当 target 大于等于 sum 时,target - sum 的值,并不断更新(取最小值),diff 初始值设置为 INT_MAX

补充说明

注意点中的 第 3 点 中,diff 不断更新取最小值的原因是 题目要求在数组找到两个数的和最接近目标值但不超过目标值,diff = min(differ, target - sum)

举栗

nums = [-18,-4,-6,13,4,4,16,-8],target = 6 为例子,如下分析:

1、原始数组

2、排序之后

3、采用双指针

4、定义 diff

5、查找过程如下 动图

Show me the Code

c++
代码语言:javascript
复制
int closestTargetValue(int target, vector<int> &array) {
    int size = array.size();
    if (size < 2) {
        return -1;
    }

    sort(array.begin(), array.end());
    int left = 0, right = size - 1, diff = INT_MAX;
    while (left < right) {
        int sum = array[left] + array[right];
        if (sum > target) {
            right--;
        } else {
            diff = min(diff, target - sum);
            left++;
        }
    }
    return diff == INT_MAX ? -1 : target - diff;
}
java
代码语言:javascript
复制
int closestTargetValue(int target, int[] array) {
    int size = array.length;
    if (size < 2) {
        return -1;
    }

    Arrays.sort(array);
    int left = 0, right = size - 1, diff = Integer.MAX_VALUE;
    while (left < right) {
        int sum = array[left] + array[right];
        if (sum > target) {
            right--;
        } else {
            diff = Math.min(diff, target - sum);
            left++;
        }
    }
    return diff == Integer.MAX_VALUE ? -1 : target - diff;
}

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2021-04-17,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 程序员小熊 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1478 · 最接近target的值
    • 解题思路
      • 注意点
        • 补充说明
          • 举栗
            • Show me the Code
              • c++
              • java
          领券
          问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档