兩數(shù)之和
問(wèn)題描繪：
給定一個(gè)整數(shù)數(shù)組nums和一個(gè)目標(biāo)值target，請(qǐng)你在該數(shù)組中找出和為目標(biāo)值的那兩個(gè)整數(shù)，并回來(lái)他們的數(shù)組下標(biāo)。
你可以假定每種輸入只會(huì)對(duì)應(yīng)一個(gè)答案。但是，數(shù)組中同一個(gè)元素不能運(yùn)用兩遍。
示例:
給定nums=[2,7,11,15],target=9
由于nums[0]+nums[1]=2+7=9
所以回來(lái)[0,1]
代碼：
packagealgorithm;
importjava.util.Arrays;
importjava.util.HashMap;
importjava.util.Map;
importjava.util.Scanner;
publicclassSolution{
//解法1：暴力法
publicint[]twoSum(int[]nums,inttarget){
inti,j;
intsum;
//外層循環(huán)遍歷每一個(gè)元素
for(i=0;i<=nums.length;i++){
//內(nèi)層循環(huán)遍歷除i以外的值
//并判別是否存在一個(gè)值與nums[i]之和等于target
for(j=i+1;j<=nums.length;j++){
sum=nums[i]+nums[j];
if(sum==target){
returnnewint[]{i,j};
}
}
}
thrownewIllegalArgumentException(“Notwosumsolution”);
}
//解法2兩遍哈希表
publicint[]twoSum_1(int[]nums,inttarget){
Mapmap=newHashMap<>();
//第一個(gè)循環(huán)，將數(shù)據(jù)元素的值和索引存到哈希表中
for(inti=0;i<nums.length;i++){
map.put(nums[i],i);
}
//第二個(gè)循環(huán)，遍歷各元素與目標(biāo)值target的差值，是否存在于哈希表中
//存在則輸出該值與差值的索引值
for(inti=0;i<nums.length;i++){
intcomplement=target-nums[i];
if(map.containsKey(complement)&&map.get(complement)!=i){
returnnewint[]{i,map.get(complement)};
}
}
thrownewIllegalArgumentException(“Notwosumsolution”);
}
//解法3一遍哈希表
//在迭代并將元素刺進(jìn)到哈希表中的同時(shí)，先校驗(yàn)哈希表中是否存在當(dāng)時(shí)元素所對(duì)應(yīng)的目標(biāo)元素，如果有則直接回來(lái)
publicint[]twoSum_2(int[]nums,inttarget){
Mapmap=newHashMap<>();
for(inti=0;i<nums.length;i++){
intcomplement=target-nums[i];
if(map.containsKey(complement)){
returnnewint[]{i,map.get(complement)};
}
map.put(nums[i],i);
}
thrownewIllegalArgumentException(“Notwosumsolution”);
}
//main
publicstaticvoidmain(String[]args){
Solutionsolution=newSolution();
Scannerinput=newScanner(System.in);
System.out.println(“請(qǐng)輸入數(shù)組長(zhǎng)度：”);
intn=input.nextInt();
int[]nums=newint[n];
for(inti=0;i<n;i++){
System.out.println(“輸入第”+i+”個(gè)數(shù)：”);
nums[i]=input.nextInt();
}
System.out.println(“請(qǐng)輸入目標(biāo)值：”);
intm=input.nextInt();
inttarget=m;
System.out.println(“目標(biāo)值：”+target);
System.out.println(“整數(shù)數(shù)組nums=”+Arrays.toString(nums));
//計(jì)算一個(gè)方法執(zhí)行時(shí)長(zhǎng)，可用模板來(lái)寫
longstartTime=System.currentTimeMillis();
//int[]twoSum=solution.twoSum(nums,target);
//int[]twoSum_1=solution.twoSum_1(nums,target);
int[]twoSum_2=solution.twoSum_2(nums,target);
longendTime=System.currentTimeMillis();
floatexcTime=(float)(endTime-startTime)/1000;
System.out.println(“結(jié)果=”+Arrays.toString(twoSum_2)+”，執(zhí)行時(shí)間=”+excTime+’s’);
}
}