剑指Offer(四十二):和为S的两个数字

  • 3
  • 216 °C
  • A+
所属分类:剑指Offer
摘要

输入一个递增排序的数组和一个数字S,在数组中查找两个数,是的他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的。

剑指Offer(四十二):和为S的两个数字

一、前言

本系列文章为《剑指Offer》刷题笔记。

刷题平台:牛客网

书籍下载:共享资源

二、题目

输入一个递增排序的数组和一个数字S,在数组中查找两个数,是的他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的。

输出描述:

对应每个测试案例,输出两个数,小的先输出。

1、思路

对于一个数组,我们可以定义两个指针,一个从左往右遍历(pleft),另一个从右往左遍历(pright)。首先,我们比较第一个数字和最后一个数字的和curSum与给定数字sum,如果curSum < sum,那么我们就要加大输入值,所以,pleft向右移动一位,重复之前的计算;如果curSum > sum,那么我们就要减小输入值,所以,pright向左移动一位,重复之前的计算;如果相等,那么这两个数字就是我们要找的数字,直接输出即可。

这么做的好处是,也保证了乘积最小。

2、代码

C++:

PS:今天发现能放表情啊。😘😘😘

Jack Cui

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

目前评论:3   其中:访客  2   博主  1

    • avatar 到底对不对 来自天朝的朋友 谷歌浏览器 Windows 10 上海市 上海理工大学 4

      为啥这样乘积最小?
      —-均值不等式

      • avatar 到底对不对 来自天朝的朋友 谷歌浏览器 Windows 10 上海市 上海理工大学 4

        如果不用遍历,必然会漏掉一些组合,如果问题存在唯一解, 在这种移动方式下,怎么保证解不再漏掉的组合里呢?