1. 兩數(shù)之和

題目

題解

暴力枚舉

直接遍歷出所有的可能性，一一比較。

class?Solution?{
????public?int[]?twoSum(int[]?nums,?int?target)?{
????????int?length?=?nums.length;
????????for?(int?i?=?0;?i?1;?i++)?{
????????????for?(int?j?=?i?+?1;?j?????????????????if?(nums[i]?+?nums[j]?==?target)?{
????????????????????return?new?int[]{i,?j};
????????????????}
????????????}

????????}
????????return?null;
????}
}

很顯然這種方式不會(huì)很快，因?yàn)殡p層遍歷，時(shí)間復(fù)雜度為 。

哈希表

只需要將已經(jīng)遍歷過的值放在 Hash 表中。

K：存放 target - 當(dāng)前值 V：存放當(dāng)前 index

這樣只需要判斷是否在 Hash 表中即可。

class?Solution?{
????public?int[]?twoSum(int[]?nums,?int?target)?{

????????HashMap?map?=?new?HashMap<>();
????????for?(int?i?=?0;?i?
????????????if?(map.get(nums[i])?!=?null)?{
????????????????return?new?int[]{map.get(nums[i]),?i};
????????????}
????????????map.put(target?-?nums[i],?i);
????????}

????????return?new?int[]{-1,?-1};
????}
}

- -