100题_10|100题_10 在排序数组中查找和为给定值的两个数字
题目：输入一个已经按升序排序过的数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字。要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字，输出任意一对即可。
例如输入数组1、2、4、7、11、15和数字15。由于4+11=15，因此输出4和11。 【100题_10|100题_10 在排序数组中查找和为给定值的两个数字】
仔细想想，你会发现对于排好序的数组来说，直接贪心就可以了。最初我们找到数组的第一个数字和最后一个数字。当两个数字的和大于输入的数字时，把较大的数字往前移动；当两个数字的和小于数字时，把较小的数字往后移动；当相等时，打完收工。这样扫描的顺序是从数组的两端向数组的中间扫描。这可以用反证法来证明。
代码如下：
文章图片
文章图片
代码 #include
<
iostream
>
using namespace
std;
bool
Find(
int
a[],
int
n,
const int &
sum,
int &
x,
int &
y)
{
int
i
= 0
, j
=
n
-
1
, csum;
while
(i
<
j)
{
csum
=
a[i]
+
a[j];
if
(csum
==
sum)
{
x
=
a[i];
y
=
a[j];
return true
;
}
else if
(csum
<
sum)
i
++
;
else
j
--
;
}
return false
;
}
int
main()
{
int
a[]
=
{
1
,
4
,
7
,
11
,
15
};
int
x, y;
if
(Find(a,
5
,
15
, x, y))
cout
<<
x
<<
" "
<<
y
<<
endl;
return 0
;
}
推荐阅读
- parallels|parallels desktop 解决网络初始化失败问题
- 你到家了吗
- 闲杂“细雨”
- 杜月笙的口才
- 赢在人生六项精进二阶Day3复盘
- jhipster|jhipster 升级无效问题
- 祖母走了
- 樱花雨
- 眼观耳听美食的日子
- “成长”读书社群招募