從今天開始返干，寫一下我在刷 LeetCode 時(shí)的心得體會(huì)激涤，包括自己的思路和別人的優(yōu)秀思路微王，歡迎各種監(jiān)督鞍埂兼耀！ 2016/10/9
編程語(yǔ)言是 Java，代碼托管在我的 GitHub 上求冷，包括測(cè)試用例瘤运。歡迎各種批評(píng)指正！
<br />
題目 —— Two Sum
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
<br >
解答
題目大意
給出一個(gè)整型數(shù)組匠题，給出一個(gè)特定的數(shù) target拯坟，返回和等于 target 的兩數(shù)下標(biāo)，假設(shè)每次輸入只有一組解梧躺。-
解題思路
- 首先似谁，我能想到最簡(jiǎn)單的思路就是兩個(gè) for 循環(huán)，遍歷整個(gè)數(shù)組掠哥，n 平方的時(shí)間復(fù)雜度巩踏，這個(gè)思路就不再寫了，很容易续搀。
-
看了一下標(biāo)簽塞琼，發(fā)現(xiàn)是
Array和Hash Table，結(jié)合討論區(qū)的朋友們解答禁舷，理解了如下思路：- 創(chuàng)建一個(gè) int 數(shù)組 result 存放需要返回的下標(biāo)彪杉，因?yàn)橹恍枰祷貎蓚€(gè)毅往，所以數(shù)組大小為 2。
- 創(chuàng)建一個(gè) HashMap<Integer, Integer> 類型的變量 map派近，key 存放數(shù)值攀唯，value 存放下標(biāo)。
- 循環(huán)遍歷數(shù)組 nums渴丸，判斷在 map 中是否存在 target-nums[i]：若存在侯嘀，直接將兩個(gè)下標(biāo)存入 result 數(shù)組，并返回谱轨；若不存在戒幔，將 nums[i] 的值和下標(biāo)放入 map，進(jìn)入下一次循環(huán)土童。
代碼實(shí)現(xiàn)
public class Solution {
public int[] twoSum(int[] nums, int target) {
int[] result = new int[2];
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(target - nums[i])) {
result[1] = i;
result[0] = map.get(target - nums[i]);
return result;
}
map.put(nums[i], i);
}
return result;
}
}
-
小結(jié)
用 HashMap 解決問(wèn)題的好處是诗茎，只需要遍歷一次數(shù)組，時(shí)間復(fù)雜度為 O(n)献汗。但難點(diǎn)在于敢订，不容易想到這種方法。我們考慮從每次輸入只有一組解這句話入手雀瓢，所以數(shù)組中肯定沒(méi)有重復(fù)的值枢析，從而使問(wèn)題迎刃而解。
另外有個(gè)小細(xì)節(jié)刃麸，如果想順序輸出下標(biāo)的話，需要把 i 賦值給 result[1]司浪，因?yàn)槲覀冊(cè)谙?map 中添加元素的時(shí)候泊业，是順序添加的，這個(gè)可以自己輸入體會(huì)一下啊易。
