AcWing 800. 数组元素的目标和
原题链接
简单
作者:
bigbrox
,
2023-10-09 17:31:18
,
所有人可见
,
阅读 61
Java代码
方法一:双指针算法
import java.util.*;
import java.io.*;
public class Main{
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] line = br.readLine().split(" ");
int n = Integer.parseInt(line[0]), m = Integer.parseInt(line[1]), x = Integer.parseInt(line[2]);
Map<Integer, Integer> map = new HashMap<>();
line = br.readLine().split(" ");
int[] a = new int[n], b = new int[m];
for(int i = 0; i < n; i ++){
a[i] = Integer.parseInt(line[i]);
}
line = br.readLine().split(" ");
for(int i = 0; i < m; i ++){
b[i] = Integer.parseInt(line[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){
System.out.printf("%d %d\n", i, j);
break;
}
}
}
}
方法二:哈希表解法
import java.util.*;
import java.io.*;
public class Main{
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] line = br.readLine().split(" ");
int n = Integer.parseInt(line[0]), m = Integer.parseInt(line[1]), x = Integer.parseInt(line[2]);
Map<Integer, Integer> map = new HashMap<>();
line = br.readLine().split(" ");
for(int i = 0; i < n; i ++){
map.put(Integer.parseInt(line[i]), i);
}
line = br.readLine().split(" ");
for(int i = 0; i < m; i ++){
int t = Integer.parseInt(line[i]), ds = x - t;
if(map.containsKey(ds)){
System.out.println(map.get(ds) + " " + i);
return;
}
}
}
}
%%%