65、【数组】acwing 800. 数组元素的目标和——滑动窗口(c++版本)-爱代码爱编程
题目描述
解题思路
先通过暴力解,可以得到答案输出。因A和B各自具有单调性(单调递增),因此可利用A和B的单调性,分别从A的头部和B的尾部移动,当找到Ai + Bj > x
时,移动B的右端指针,往左移。当找到时Ai + Bj == x
,输出i
和j
。
注:需要从A和B相反的两端走才行,不能各从A和B的首部开始寻找,若各自从首部开始走,可能会把更小的一个有效数移过。
解题算法
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n, m, x, a[N], b[N];
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, j = m - 1; i < n; i++) {
while(j >= 0 && a[i] + b[j] > x) j--;
if(a[i] + b[j] == x) printf("%d %d", i, j);
}
return 0;
}
时间复杂度 O ( n + m ) O(n + m) O(n+m)
原题链接:800. 数组元素的目标和