Question

检测数组里是否有两个数之和等于某个数

Answer 1

[算法C++]
检测数组里是否有两个数之和等于某个数
解决方法一：先将数组排序，然后从两头开始遍历
数组排序后，从左端开始取最小值，从右端取最大值，
判断两者之和与目标的大小：
1.
等于时，输出两个数；
2.
大于时，右端移到第2个数，继续判断；
3.
小于时，左端移到第2个数，继续判断。
#include
#include
#include
using
namespace
std;
void
fun1(int
a[],
int
length,
int
target)
{
//
给数组排序
sort(a,
a
+
length);
//
left是最小值，right是最大值
int
left
=
0,
right
=
length
-
1;
while
(left
<
right)
{
int
tmp
=
a[left]
+
a[right];
if
(tmp
==
target)
{
cout
<<
a[left]
<<
a[right]
<<
endl;
return;
}
else
if
(tmp
>
target)
{
//
和比目标大，就减小right，从而减小和
right--;
}
else
{
//
和比目标小，就增大left，从而增大和
left++;
}
}
cout
<<
无
<<
endl;
}
int
main()
{
int
a[]
=
{
1,
3,
2,
7,
6,
9,
8,
0,
5,
4
};
int
target
=
0;
while
(cin
>>
target)
{
fun1(a,
10,
target);
}
}
上述方法虽然简单，但弊端也有，没法输出所有等于目标值的两个数。
解决方法二：
暴力解法，记录下每一个数与其他数的和放在一个二维数组里，然后遍历即可，这样可以记录下所有的和等于目标值的数值对，如下：
假设输入数组为:
2
3
4
5
1
有如下矩阵：
2
3
4
5
1
2
-
5
6
7
3
3
5
-
7
8
4
4
6
7
-
9
5
5
7
8
9
-
6
1
3
4
5
6
-
当目标值为7时，就有两组：
（5,2）与（3,4）
考虑到对称性，有n[i][j]
=
n[j][i],i!=j,
，所以，我们只需要i>j的数值对就行。
void
fun2(int
a[],
int
length,
int
target)
{
int**
n
=
new
int*[length];
for
(int
i
=
0;
i
<
length;
i++)
{
n[i]
=
new
int[length];
}
for
(int
i
=
0;
i
<
length;
i++)
{
for
(int
j
=
length
-
1;
j
>
i;
j--)
{
n[i][j]
=
n[j][i]
=
a[i]
+
a[j];
}
}
for
(int
i
=
0;
i
<
length;
i++)
{
for
(int
j
=
length
-
1;
j
>
i;
j--)
{
if
(n[i][j]
==
target)
{
cout
<<
a[i]
<<
<<
a[j]
<<
endl;
}
}
}
}