AcWing 800. 数组元素的目标和

本文主要是介绍AcWing 800. 数组元素的目标和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem: AcWing 800. 数组元素的目标和

文章目录

思路
解题方法
复杂度
Code

思路

这是一个双指针问题。我们有两个排序数组，我们需要找到两个数，一个来自每个数组，它们的和等于目标值。我们可以在第一个数组中从左到右遍历，同时在第二个数组中从右到左遍历。如果当前的和大于目标值，我们就将第二个数组的指针向左移动；如果当前的和小于目标值，我们就将第一个数组的指针向右移动。当找到和等于目标值的两个数时，我们就可以停止遍历。

解题方法

初始化两个指针，一个指向第一个数组的开始，另一个指向第二个数组的结束。
遍历第一个数组，对于每个元素，检查它与第二个数组当前元素的和是否等于目标值。
如果和大于目标值，将第二个数组的指针向左移动。
如果和小于目标值，将第一个数组的指针向右移动。
如果找到和等于目标值的两个数，打印它们的索引并停止遍历。

复杂度

时间复杂度:

$O (n + m)$ ，其中 n 和 m 分别是两个数组的长度。在最坏的情况下，我们可能需要遍历两个数组的所有元素。

空间复杂度:

$O (1)$ ，我们只使用了常数级别的额外空间。

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;public class Main {static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static StreamTokenizer sr = new StreamTokenizer(in);static int MAXN = (int) (1e5 + 10);static int[] arr1 = new int[MAXN];static int[] arr2 = new int[MAXN];static int n, m, x;public static void main(String[] args) throws IOException {n = nextInt();m = nextInt();x = nextInt();for (int i = 0; i < n; i++) {arr1[i] = nextInt();}for (int i = 0; i < m; i++) {arr2[i] = nextInt();}for (int i = 0, j = m - 1; i < n; i++) {while (j >= 0 && arr1[i] + arr2[j] > x)j--;if (arr1[i] + arr2[j] == x) {out.printf("%d %d\n", i, j);break;}}out.flush();}static int nextInt() throws IOException {sr.nextToken();return (int) sr.nval;}}