Question:查找两个总和为特定值的索引(java)
·
题目:

解一:输入数组长度n,哈希数组:用来存元素的“下标”,长度205是元素范围大概在-100~100之间(加100后变成0~200),for循坏输入第i个元素,把元素“偏移100”后作为hash的下标,存当前元素的下标i。例:元素是-20,加100后对应hash[80]。要找的另一个数是k-arr[i],检查其对应的hash位置是否有值,有的话输出两个对应的下标,结束程序。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n=scan.nextInt();
int[] arr=new int[n+1];
int[] hash=new int[205];//存放元素的位置
for(int i=0;i<n;i++){
arr[i]=scan.nextInt();
hash[arr[i]+100]=i;//比如-20对应hash[80]
}
int k=scan.nextInt();
for(int i=0;i<n;i++) {
if(hash[k-arr[i]+100]!=0) {//相应的元素存在
System.out.println(i+" "+hash[k-arr[i]+100]);
return;
}
}
scan.close();
}
}
解二:输入数组长度n,循坏n次,把输入的数存到list里,输入目标值k,检查list中是否有“k-当前元素”这个数,有的话将当前元素下标存到indexs中。接着对下标列表排列,取第一个符合条件的下标作为index1,找“k-list.get(index1)”对应的元素的下标,赋值给index2,最后进行输出。
import java.util.Scanner;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int nextInt1 = sc.nextInt();
ArrayList<Integer> list = new ArrayList<Integer>();
for(int i = 0;i<nextInt1;i++) {
int nextInt2 = sc.nextInt();
list.add(nextInt2);
}
int nextInt3 = sc.nextInt();
ArrayList<Integer> indexs = new ArrayList<Integer>();
int index1;
int index2 = -1;
for(int j = 0;j<list.size();j++) {
if (list.contains(nextInt3 - list.get(j))) {
indexs.add(j);
}
}
indexs.sort(Comparator.naturalOrder());
index1 = indexs.get(0);
for(int k = 0;k<list.size();k++) {
if (list.get(k) == nextInt3 - list.get(index1)) {
index2 = k;
}
}
System.out.println(index1+" "+index2);
}
}
解三(自己的解法):输入数组长度,for循坏遍历将输入的数存到数组中,获取目标值,设立计数器(最后得到索引最小的一组),和最后的两个索引。双重遍历:如果与目标值相等的话,并且两下标和小于计数器的值,则进行相应的赋值,最后输出。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();//输入数组长度
int x[] = new int[n];//建立数组
for (int i = 0;i<x.length;i++){//for循坏遍历获取数组内容
x[i] = scanner.nextInt();
}
int end = scanner.nextInt();//获取指定值
int count = 2*n;//设立计数器,最后得到索引最小的一组
int endi = 0,endj = 0;//最后的两个索引
for (int i =0;i<x.length;i++){//双重遍历
for (int j = 0;j<x.length;j++){
if (x[i]+x[j] == end){//如果与特定值相等的话
if ((i+j)<count) {//如果索引组小于的话进行赋值
count = i + j;
endi = i;
endj = j;
}
}
}
}
System.out.println(endi + " "+ endj);
scan.close();
}
}
更多推荐

所有评论(0)