OnlineJ两数之和
题目描述
给定一个从小到大的数组和一个目标数t，在其中找到两个数，使得两数之和与目标数相等，输出两个数在数组中的位置。
输入
第一行输入两个整数 n, t（1 ≤ n ≤ 1000000, 1 ≤ t ≤ 20000000）
接下来一行 n 个数，均小于10,000,000
输出
输出两个用空格隔开的数表示位置（从零开始计数），答案有唯一解
1.暴力法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #include<iostream>
#include<cstdio>
using namespace std;
int num[1000005];
int n, target;
int main() {
scanf("%d%d", &n, &target);
for (int i = 0; i < n; ++i) {
scanf("%d", &num[i]);
}
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (num[i] + num[j] == target) {
cout << i << " " << j << endl;
return 0;
}
}
}
cout << "not fimd" << endl;
return 0;
}
|
注意：由于数据范围(1≤n≤1000000, 1≤t≤20000000)，暴力枚举的时间复杂度为O(n^2)一定会超时，空间复杂度为O(1)
2.二分法：
==思路==：
- 使用for循环遍历数组中的每一个数字
- 在循环体内部，使用target值减去当前遍历的数字值（结果为配对值），在数组中二分查找该数字
- 如果找到配对值则输入答案，否则没有配对值输出nofind
复杂度分析：使用二分查找程序的时间复杂为O(nlogn)、空间复杂度为O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| #include<iostream>
#include<cstdio>
using namespace std;
int num[1000005];
int n, target;
int main(){
scanf("%d%d", &n, &target);
for(int i = 0; i < n; ++i){
scanf("%d", &num[i]);
}
for(int i = 0; i < n; ++i){
int temp = target - num[i];
int l = i + 1, r = n - 1;
while(l <= r){
int mid = (l + r) / 2;
if(temp == num[mid]){
cout << i << " " << mid << endl;
return 0;
}
if(temp < num[mid]){
r = mid - 1;
}else{
l = mid + 1;
}
}
}
cout << "not fimd" << endl;
return 0;
}
|
3.双指针法：
==思路==：
- 分别初始化两个指针，指向数组的起始和结尾
- 将数组头尾元素相加sum值与target值比较：
如果sum>target（数据偏大），则将右指针向左移动一位
如果sum<target（数据偏小），则将左指针向右移动一位
如果sum==target（找到结果），直接输出左右指针
- 当左右指针错开时，target查找结束（数组遍历完成没有找到结果nofind）
复杂度分析：使用双指针法的时间复杂度为O(n)，空间复杂度为O(1)，是一种效率比较高的解法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| #include<iostream>
#include<cstdio>
using namespace std;
int num[1000005];
int n, target;
int main(){
scanf("%d%d", &n, &target);
for(int i = 0; i < n; ++i){
scanf("%d", &num[i]);
}
int l = 0, r = n - 1;
while(l < r){
int t = num[l] + num[r];
if(t == target){
printf("%d %d\n", l, r);
return 0;
}
if(t > target){
r--;
}else{
l++;
}
}
printf("no find\n");
return 0;
}
|
4.哈希表：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #include<iostream>
using namespace std;
int n, target;
int num[1000005], mark[1000005];
int main() {
scanf("%d%d", &n, &target);
for (int i = 1; i <= n; ++i) {
scanf("%d", &num[i]);
mark[num[i]] = i;
}
for (int i = 1; i <= n; ++i) {
int temp = target - num[i];
if (mark[temp] != 0) {
printf("%d %d\n", i - 1, mark[temp] - 1);
return 0;
}
}
printf("no find!\n");
return 0;
}
|
注意：时间复杂度为O(n)、空间复杂度为O(n)
3.问题总结：
两数之和问题，四种解法时空复杂分析,
在不限空间的情况下，最快的方法是哈希表法时间复杂度为O(n)：
