題目：
題目地址：https://leetcode-cn.com/problems/two-sum/
問(wèn)題描述：
給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)目標(biāo)值 target，請(qǐng)你在該數(shù)組中找出和為目標(biāo)值的那 兩個(gè) 整數(shù)兔综，并返回他們的數(shù)組下標(biāo)饿凛。
你可以假設(shè)每種輸入只會(huì)對(duì)應(yīng)一個(gè)答案。但是软驰，你不能重復(fù)利用這個(gè)數(shù)組中同樣的元素涧窒。
示例:
給定 nums = [2, 7, 11, 15], target = 9
因?yàn)?nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]
我的解題思路：
1.暴力解法
最容易想到的就是雙層for循環(huán)，遍歷元素進(jìn)行相加锭亏，判斷和是否等于target纠吴，如果是則return這兩個(gè)下標(biāo)組成的數(shù)組。如果遍歷完沒(méi)有符合的結(jié)果慧瘤，則return null 戴已。
public int[] twoSum(int[] nums, int target) {
for (int i = 0; i <nums.length ; i++) {
for (int j = 0; j <nums.length; j++) {
if (nums[i]+nums[j]==target){
return new int[]{i,j};
}
}
}
return null;
}
時(shí)間復(fù)雜度：O(n2)
空間復(fù)雜度：O(1)
2.嘗試著優(yōu)化（實(shí)際上并沒(méi)有優(yōu)化成功）
暴力解法能通過(guò)測(cè)試，但是性能是最差的锅减，于是嘗試著想要優(yōu)化糖儡。
一開(kāi)始想著的優(yōu)化思路是減少for循環(huán)的次數(shù)，想到了如果出現(xiàn) target>nums[i] 那么nums[i]+nums[j]==target就不成立了怔匣，這樣就沒(méi)有必要進(jìn)入第二層for握联，這樣可以稍微提高性能。于是寫(xiě)下了：
for (int i = 0; i <nums.length ; i++) {
//一開(kāi)始覺(jué)得：如果數(shù)組中某元素大于target每瞒，則沒(méi)有比較進(jìn)入第二層for金闽，直接break
if (nums[i]>target){
break;
}
for (int j = 0; j <nums.length; j++) {
if (nums[i]+nums[j]==target){
return new int[]{i,j};
}
}
}
return null;
}
提交了之后并沒(méi)有通過(guò)。原來(lái)忘記考慮測(cè)試用例中有負(fù)數(shù)的存在剿骨，覺(jué)得應(yīng)該要用絕對(duì)值比較代芜，于是修改如下了：
if (Math.abs(nums[i])>Math.abs(target)){
break;
}
然而，提交了之后還是沒(méi)有通過(guò)浓利。事實(shí)上是我沒(méi)有考慮到一些復(fù)雜的測(cè)試用例挤庇，上面的寫(xiě)法只能通過(guò)nums數(shù)組中全是正數(shù)或者全是負(fù)數(shù)的測(cè)試用例钞速，而nums數(shù)組中既存正整數(shù)又存在負(fù)數(shù)的情況是通過(guò)不了的。
于是我的嘗試優(yōu)化失敗罚随。
那么還是看看官方給出的解題思路吧玉工。
官方解題思路：
方法一：暴力法
暴力法很簡(jiǎn)單，遍歷每個(gè)元素 xx淘菩，并查找是否存在一個(gè)值與 target - x相等的目標(biāo)元素遵班。
class Solution {
public int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] == target - nums[i]) {
return new int[] { i, j };
}
}
}
throw new IllegalArgumentException("No two sum solution");
}
}
復(fù)雜度分析：
時(shí)間復(fù)雜度：O(n^2)， 對(duì)于每個(gè)元素潮改，我們?cè)噲D通過(guò)遍歷數(shù)組的其余部分來(lái)尋找它所對(duì)應(yīng)的目標(biāo)元素狭郑，這將耗費(fèi) O(n) 的時(shí)間。因此時(shí)間復(fù)雜度為 O(n^2)汇在。
空間復(fù)雜度：O(1)翰萨。
方法二：兩遍哈希表
為了對(duì)運(yùn)行時(shí)間復(fù)雜度進(jìn)行優(yōu)化，我們需要一種更有效的方法來(lái)檢查數(shù)組中是否存在目標(biāo)元素糕殉。如果存在亩鬼，我們需要找出它的索引。保持?jǐn)?shù)組中的每個(gè)元素與其索引相互對(duì)應(yīng)的最好方法是什么阿蝶？哈希表雳锋。
通過(guò)以空間換取速度的方式，我們可以將查找時(shí)間從 O(n)降低到 O(1)羡洁。哈希表正是為此目的而構(gòu)建的玷过，它支持以 近似 恒定的時(shí)間進(jìn)行快速查找。我用“近似”來(lái)描述筑煮，是因?yàn)橐坏┏霈F(xiàn)沖突辛蚊，查找用時(shí)可能會(huì)退化到 O(n)。但只要你仔細(xì)地挑選哈希函數(shù)真仲，在哈希表中進(jìn)行查找的用時(shí)應(yīng)當(dāng)被攤銷(xiāo)為 O(1)袋马。
一個(gè)簡(jiǎn)單的實(shí)現(xiàn)使用了兩次迭代。在第一次迭代中秸应，我們將每個(gè)元素的值和它的索引添加到表中飞蛹。然后，在第二次迭代中灸眼，我們將檢查每個(gè)元素所對(duì)應(yīng)的目標(biāo)元素target?nums[i]）是否存在于表中。注意墓懂，該目標(biāo)元素不能是 nums[i]本身焰宣！
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], i);
}
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement) && map.get(complement) != i) {
return new int[] { i, map.get(complement) };
}
}
throw new IllegalArgumentException("No two sum solution");
}
}
復(fù)雜度分析：
時(shí)間復(fù)雜度：O(n)， 我們把包含有 n個(gè)元素的列表遍歷兩次捕仔。由于哈希表將查找時(shí)間縮短到 O(1) 匕积，所以時(shí)間復(fù)雜度為 O(n)盈罐。
空間復(fù)雜度：O(n)， 所需的額外空間取決于哈希表中存儲(chǔ)的元素?cái)?shù)量闪唆，該表中存儲(chǔ)了 n 個(gè)元素盅粪。
方法三：一遍哈希表
事實(shí)證明，我們可以一次完成悄蕾。在進(jìn)行迭代并將元素插入到表中的同時(shí)票顾，我們還會(huì)回過(guò)頭來(lái)檢查表中是否已經(jīng)存在當(dāng)前元素所對(duì)應(yīng)的目標(biāo)元素。如果它存在帆调，那我們已經(jīng)找到了對(duì)應(yīng)解奠骄，并立即將其返回。
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[] { map.get(complement), i };
}
map.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
}
}
復(fù)雜度分析：時(shí)間復(fù)雜度：O(n)番刊， 我們只遍歷了包含有n 個(gè)元素的列表一次含鳞。在表中進(jìn)行的每次查找只花費(fèi) O(1)的時(shí)間。
空間復(fù)雜度：O(n)芹务， 所需的額外空間取決于哈希表中存儲(chǔ)的元素?cái)?shù)量蝉绷，該表最多需要存儲(chǔ) n 個(gè)元素。
總結(jié)：
-
要仔細(xì)讀題枣抱。
題目中寫(xiě)道：”你不能重復(fù)利用這個(gè)數(shù)組中同樣的元素熔吗。“在官方解題中第二層for循壞是 j=i+1 起始，而我自己寫(xiě)的是普通的 j=0 起始沃但，這樣做了很多次無(wú)用的循壞磁滚。
沒(méi)有仔細(xì)讀題，寫(xiě)個(gè)暴力法的性能都比官方題解寫(xiě)的差宵晚。
-
關(guān)于返回結(jié)果
當(dāng)沒(méi)有符合預(yù)期的結(jié)果時(shí)垂攘，我一開(kāi)始使用的是 return null。但是這其實(shí)并不是一個(gè)好的編程習(xí)慣淤刃，在開(kāi)發(fā)中晒他，這種做法會(huì)把問(wèn)題丟給方法的調(diào)用者，容易造成NPE逸贾。更好的做法應(yīng)該是像官方題解中一樣陨仅，throw出異常。
要盡可能的考慮更多的測(cè)試用例情況铝侵。
-
哈希表的妙用
哈希表用空間換時(shí)間灼伤，能將查找時(shí)間從 O(n)降低到 O(1)，查找的性能非常優(yōu)秀咪鲜。
最后：
第一次刷LeetCode狐赡，雖然是簡(jiǎn)單的題目，但還是暴露了很多問(wèn)題疟丙。但正是遇見(jiàn)問(wèn)題颖侄，才會(huì)有收獲鸟雏。
