数组元素的目标和

题目描述
求A[i] + B[j] == k 的 (i , j) 对

样例
输入

4 5 6
1 2 4 7
3 4 6 8 9
输出

1 1
算法1
(双指针) O(n)O(n)
i从 0开始 从前往后遍历
j从 m - 1开始 从后向前遍历

和纯暴力的O(n2)O(n2) 算法的区别就在于

j指针不会回退

C++ 代码
#include
#include
using namespace std;

const int N = 1e5 + 10;

int n, m, k;
int a[N], b[N];
#define read(x) scanf(“%d”,&x)

int main()
{
read(n), read(m), read(k);
for (int i = 0; i < n; i ++ ) read(a[i]);
for (int i = 0; i < m; i ++ ) read(b[i]);

for (int i = 0, j = m - 1; i < n; i ++) {
    while(j >= 0 && a[i] + b[j] > k) j --;
    if(j >= 0 && a[i] + b[j] == k) printf("%d %d\n", i, j);
}
return 0;
1
2
3
4
5

}

双指针的核心：将上一状态指针所表达的信息传递至下一状态，从而减少无谓的搜索。

对于任意A[i]+B[j]>X， A，B单调递增，则显然，A[i+1]+B[j]>A[i]+B[j]>X。因此，指针j应该向j-1方向搜索，反之亦然。

因此对于任意的指针i，对应的指针j搜索的区域在A[i]+B[j]>X与A[i]+B[j]

N, M, X = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

i = 0
j = 0

for i in range(N):
while A[i] + B[j] > X:
j -= 1
while A[i] + B[j] < X and j < len(B) - 1:
j += 1
if A[i] + B[j] == X:
break

print(i, j)

代码
//
// Created by Genes on 2020/12/6.
//
#include

#define ios
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr)

using namespace std;

const int N = 1e5 + 10;

int n, m, x;
int a[N], b[N];

int main() {
ios;
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 (a[i] + b[j] > x && j >= 0) {
j–;
}
if (a[i] + b[j] == x) {
cout << i << " " << j << endl;
break;
}
}
return 0;
}
#include
#include
#include

using namespace std;

const int N = 1e5+10;

int a[N],b[N];

int main()
{
int n,m,x;
cin>>n>>m>>x;
for(int i=0;i>a[i];
for(int j=0;j>b[j];

int j=0;
for(int i=0;i>1;
        if(b[mid]>=k)   r=mid;
        else l=mid+1;
    }
    // cout<

for(int i=0,j=m-1;ix) j--;
    if(a[i]+b[j]