1 兩數(shù)之和
給定一個整數(shù)數(shù)組和一個目標(biāo)值豁生，找出數(shù)組中和為目標(biāo)值的兩個數(shù)譬巫。
你可以假設(shè)每個輸入只對應(yīng)一種答案组哩，且同樣的元素不能被重復(fù)利用等龙。
示例:
給定 nums = [2, 7, 11, 15], target = 9
因為 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
暴力破解法
/**
* 時間復(fù)雜度n的平方
* 空間復(fù)雜度n
*/
public int [] findIndex(int a[],int sum){
for(int i=0;i<a.length;i++){
for(int j=i+1;j<a.length;j++){
if((a[j]+a[i])==sum){
return new int[] {i,j};
}
}
}
return null;
}
空間換時間方法
/**
* 時間復(fù)雜度n
* 空間復(fù)雜度n
*/
public int [] findIndex2(int a[],int sum){
HashMap hashMap=new HashMap();
for(int i=0;i<a.length;i++){
if(hashMap.containsKey(sum-a[i])){
return new int[] {i,(int)hashMap.get(sum-a[i])};
}
hashMap.put(a[i],i);
}
return null;
}
