算法基础课题解合集
二分
二分思路
既然要找两个和为 $x$ 的数，那么我们可以把它转换成确定了一个 $y$ 为 $A_i$ 然后快速在 $B$ 中找出 $x - y$ 的问题。
显然我们可以二分查找，算法复杂度为 $O(nlogn)$，可以$AC$。
代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int a[N], b[N];
int n, m, x;
int main() {
cin >> n >> m >> x;
for (int i = 0; i < n; i ++) cin >> a[i];
for (int i = 0; i < m; i ++) cin >> b[i];
for (int i = 0; i < n; i ++) {
int y = x - a[i];
int l = 0, r = m - 1;
while (l <= r) {
int mid = l + r >> 1;
if (b[mid] == y) {
cout << i << " " << mid << endl;
return 0;
} else if (b[mid] < y) {
l = mid + 1;
} else {
r = mid - 1;
}
}
}
return 0;
}
双指针
双指针思路
我们先简化一下问题，变成求 $A_i + B_j >= x$ 且 $j$ 要最小。
我们用可以一个指针 $i$ 枚举 $A$ 中的所有数，而 $j$ 则用来枚举 $B$，但由于数组是单调递增的，所以如果 $A_i + B_j \ge x$ 那么 $B_{j + 1}$ 到 $B_m$ 就不可能是答案。
所以 $j$ 是只能递减的，如此，我们便可以用 $O(n + m)$ 的时间复杂度通过这道题。
代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int n, m, x;
int a[N], b[N];
int main() {
cin >> n >> m >> x;
for (int i = 1; i <= n; i ++) cin >> a[i];
for (int i = 1; i <= m; i ++) cin >> b[i];
for (int i = 1, j = m; i <= n; i ++) {
while (j >= 0 && a[i] + b[j] >= x) j --;
if (j >= 0 && b[j + 1] + a[i] == x) // 注意这里的下标，感谢大佬的指正
cout << i - 1 << " " << j << endl;
}
return 0;
}
哈希
思路
我们可以在输入 $A$ 时把每个数存进哈希表里，对于每个输入的 $B_i$ 看看 $x - B_i$ 是否出现与哈希表即可。
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int N = 100010;
int n, m, x;
int a[N], b[N];
unordered_map<int, int> h;
int main() {
cin >> n >> m >> x;
for (int i = 0; i < n; i ++) {
cin >> a[i];
h[a[i]] = i;
}
for (int i = 0; i < m; i ++) {
cin >> b[i];
if (h.count(x - b[i]))
cout << h[x - b[i]] << " " << i << endl;
}
return 0;
}
好啦，这篇题解到这里就结束啦！感谢观看！！！
$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\mathcal{writer\enspace by \enspace acwing}$ : $\mathfrak{天元之弈}$
大佬，第一个二分写法
if (b[mid] == y) { cout << i << " " << mid << endl; return 0;如果不return 0为什么会超时，怎么想到＋return 0的
因为这题有唯一解
例子:
2 3 5
1 3
2 2
可以知道3 + 2 = 5,3的位置是i = 1,5的位置是j = 0,而对应我们的程序运行对应的解为i = 1;j = -1
而我们的程序if (j >= 0 && b[j + 1] + a[i] == x)会把这种情况退出,从而导致无解,所以要改为if (j >= -1 && b[j + 1] + a[i] == x)
双指针算法
这数据是不是有问题，B的长度是2不是3
这是y总的测试数据，没有问题，
m = 3，说明B数组的长度就是3，但你B只有两个数，显然有问题啊
那里打错了，是二
你可以试试
2 2 3
1 2
1 3
已经修改了，强迫症不太喜欢-1，就把数组下标改了qwq
这样也可以，就是楼主的思路，稍微简洁一些
天才啊，老弟，双指针解法犀利；
感觉查找匹配还是哈希比较好写
大佬啊哈希表真的妙
双指针有点不太懂为什么等于也要j–
我咋就想不到呢
这个哈希，实在是太秀了
牛逼啊
#include [HTML_REMOVED]
#include [HTML_REMOVED]
int a[100010],b[100010];
int n,m,x;
int main()
{
scanf(“%d%d%d”,&n,&m,&x);
for(int i=0;i<n;i)
scanf(“%d”,&a[i]);
int i=0;
int j=m;
for(i=0;i<m;i)
scanf(“%d”,&b[i]);
for(i=0;i<n;i++)
{
j=x-a[i];
int l=0;
int r=m-1;
while(l<=r)//大佬为什么这里的=去掉后就得不出正确结果了？ 有点想不明白，大佬能解释一下吗
}
return 0;
}
这道题用二分的话，每个a[i]都会在b[i]进行二分查找， 最坏的时间复杂度不应该是n✖二分的复杂度nlogn吗，这样子不会超时吗
二分的复杂度是 $O(logn)$ 哦
但是你要循环n次，每次都要二分查找，时间复杂度最坏不就变成n^2*nlogn了
对呀，所以是 $O(n \times logn)$ 啊
我一次二分是 $nlogn$ 那么做 $n$ 次二分，就是 $nlogn$，可以看代码，$for$ 一共 $n$ 次，内部循环二分每次 $logn$
哦哦，我的错，你是对的OAO
二分写法里的l = mid + 1 我能理解，但为什么r = mid - 1，而不是r = mid啊，我r = mid会超时是什么原因呢
注意看我写的是 $l<=r$，这样子的模板虽然时间不如y总的（会多执行一次），但是固定一个模板，不容易错
哇，好牛，学到了个新方法，想问一下如果我想用y总的板子为什么会错呀，这个样例无输出
1 2 6
1
3 5
标准答案
0 1
你代码发我看看呗
这样是WA的为什么呢
输出反了，先输出
i再是l，注意你上面写的是b[l]和a[i]。哈希的时间复杂度是多少呢
$O(1)$
大概应该是O(N)吧
好呢
哈希一步是O(1)，循环n次就是O(n)