经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 其他 » 职业生涯 » 查看文章
好家伙,你管这破玩意叫“双指针”?
来源:cnblogs  作者:公众号程序员小熊  时间:2021/4/19 8:46:49  对本文有异议

大家好,我是 程序员小熊 ,今天给大家带来一道亚马逊的面试题,即 LintCode 1478 · 最接近target的值 ,提供 双指针 的解题思路,供大家参考,希望对大家无论是刷题还是面试都有所帮助。

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++

  1. 1 int closestTargetValue(int target, vector<int> &array) {
  2. 2 int size = array.size();
  3. 3 if (size < 2) {
  4. 4 return -1;
  5. 5 }
  6. 6
  7. 7 sort(array.begin(), array.end());
  8. 8 int left = 0, right = size - 1, diff = INT_MAX;
  9. 9 while (left < right) {
  10. 10 int sum = array[left] + array[right];
  11. 11 if (sum > target) {
  12. 12 right--;
  13. 13 } else {
  14. 14 diff = min(diff, target - sum);
  15. 15 left++;
  16. 16 }
  17. 17 }
  18. 18 return diff == INT_MAX ? -1 : target - diff;
  19. 19 }
View Code

java

  1. 1 int closestTargetValue(int target, int[] array) {
  2. 2 int size = array.length;
  3. 3 if (size < 2) {
  4. 4 return -1;
  5. 5 }
  6. 6
  7. 7 Arrays.sort(array);
  8. 8 int left = 0, right = size - 1, diff = Integer.MAX_VALUE;
  9. 9 while (left < right) {
  10. 10 int sum = array[left] + array[right];
  11. 11 if (sum > target) {
  12. 12 right--;
  13. 13 } else {
  14. 14 diff = Math.min(diff, target - sum);
  15. 15 left++;
  16. 16 }
  17. 17 }
  18. 18 return diff == Integer.MAX_VALUE ? -1 : target - diff;
  19. 19 }
View Code

原文链接:http://www.cnblogs.com/TanLiuYi00/p/fang.html

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号