题目描述
求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;
}
双指针的核心：将上一状态指针所表达的信息传递至下一状态，从而减少无谓的搜索。
对于任意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]<X之间，搜索的个数是常数的，因此总的时间复杂度为O(n)。
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<n;i++) cin>>a[i]; for(int j=0;j<m;j++) cin>>b[j];
int j=0; for(int i=0;i<n;i++) { int k=x-a[i]; int l=0,r=m-1; while(l<r) { int mid=l+r>>1; if(b[mid]>=k) r=mid; else l=mid+1; } // cout<<l<<"-----"<<endl; if(b[l]==k) { cout<<i<<" "<<l<<endl; break; } } return 0;
}
双指针
O(n)O(n) #include #include #include using namespace std; const int N = 1e6; int a[N]; int b[N]; int main() { int n,m,x; cin>>n>>m>>x; for(int i=0;i<n;i++) cin>>a[i]; for(int j=0;j<m;j++) cin>>b[j];
for(int i=0,j=m-1;i<n;) { if(a[i]+b[j]==x) {cout<<i<<" "<<j<<endl;break;} if(a[i]+b[j]>x) j--; if(a[i]+b[j]<x) i++; //if(i==j) break; } return 0;
}
