AcWing 800. 数组元素的目标和
原题链接
简单
作者:
ss_uaena
,
2021-12-30 10:15:16
,
所有人可见
,
阅读 174
- 这道题很明显通过枚举两个数组,找到数组中的某一个元素,使得他们的和等于给定值,可以使用双指针算法。
- 首先用快指针 枚举它的整个数组,慢指针从它的数组的最后一位开始向前枚举,
a. 为什么要慢指针要从最后一个数开始枚举?因为两个数组都是升序的,
b. 如果我一个数加上另一个数组的最大值,仍然小于给定值x的话,我就需要移动我自己了(快指针)。
c. 如果大于给定值的话,我就需要移动另一个数组,让它向前枚举即可找到两个数的和等于指定值,当然也存在没有找到的情况。
d. 当慢指针走到头了还没找到的话,我们也需要移动快指针了。
- 最后,发现数组元素的数组范围为 10^9,使用 BufferedReader 或者 scanf,读入数据。
code with java
import java.io.*;
public class Main {
final static int N = (int)(1e5+10);
public static void main(String[] args) throws IOException{
int[] a = new int[N];
int[] b = new int[N];
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] inputStr = br.readLine().split(" ");
int n = Integer.parseInt(inputStr[0]);
int m = Integer.parseInt(inputStr[1]);
int x = Integer.parseInt(inputStr[2]);
inputStr = br.readLine().split(" ");
for (int i = 0; i < n; i++) a[i] = Integer.parseInt(inputStr[i]);
inputStr = br.readLine().split(" ");
for (int i = 0; i < m; i++) b[i] = Integer.parseInt(inputStr[i]);
for (int i = 0, j = m - 1; i < n; i++) {
while (j >= 0 && a[i] + b[j] > x) j--;
if (j >= 0 && a[i] + b[j] == x) {
System.out.println(i + " " + j);
break;
}
}
}
}
code with c++
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n, m, x;
int a[N], b[N];
int main() {
scanf("%d%d%d", &n, &m, &x);
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
for (int i = 0; i < m; i ++ ) scanf("%d", &b[i]);
for (int i = 0, j = m - 1; i < n; i ++ ) {
while (j >= 0 && a[i] + b[j] > x) j -- ;
if (j >= 0 && a[i] + b[j] == x) cout << i << ' ' << j << endl;
}
return 0;
}