問題描述

leetcode的第一題，這種方法可以實(shí)現(xiàn)O(n)復(fù)雜度解

題目要求是給一個(gè)int[],例如 nums = [2, 7, 11, 15]，給一個(gè)target = 9。若存在兩個(gè)數(shù)的和為target值，例如 nums[0] + nums[1] = 2 + 7 = 9return [0, 1].

使用如下解法的時(shí)候，有一點(diǎn)疑惑，就是new了一個(gè)hashmap，但是并沒有給他賦值，這種情況下是如何實(shí)現(xiàn)題目要求的呢？

public int[] twoSum(int[] numbers, int target) { int[] result = new int[2]; Map<Integer, Integer> map = new HashMap<Integer, Integer>(); for (int i = 0; i < numbers.length; i++) {if (map.containsKey(target - numbers[i])) { result[1] = i + 1; result[0] = map.get(target - numbers[i]); return result;}map.put(numbers[i], i + 1); } return result;}

問題解答

for循環(huán)里面的map.put()不是賦值嗎？？？

題目是要求得兩個(gè)數(shù)的和為目標(biāo)值為給定值，那么一定要遍歷至少兩個(gè)數(shù).(1)如果先初始化，花費(fèi)算法時(shí)間O(n);然后再遍歷查找到第一正確的值時(shí),需要算法時(shí)間O(k), 0<k<n.總時(shí)間是O(n+k), 要判斷是不是自己，如(10 = 5 + 5)．這種情況實(shí)現(xiàn)是：

1)先初始化map,　 　2)遍歷第一個(gè)數(shù)2, target - 2 = 9 - 2 = 7　 3)判斷7也在map中，返回正確結(jié)果．　 注意：要遍歷到第一個(gè)正確數(shù)

　 (2)如果不縣初始化，那么一定會(huì)遍歷到第二個(gè)正確的數(shù)，才停止，算法時(shí)間為O(k)(1<k<=n).不用判斷自己．　 這種情況實(shí)現(xiàn)是：

　1)遍歷第一個(gè)數(shù)2, target - 2 = 9 - 2 = 7　2)判斷7是否在map，發(fā)現(xiàn)不在，把2加入map,繼續(xù)遍歷　3)直到遍歷到７, target - 7 = 9 - 7 = 2　4)判斷2在map,返回正確結(jié)果　注意，要遍歷到第二個(gè)正確數(shù).回答3：

沒有 Key 的情況下，HashMap.containsKey(Key) 返回的是 false 不包括 Key。

public boolean containsKey(Object key) {return getNode(hash(key), key) != null; }

不會(huì)出現(xiàn)你所想的空指針錯(cuò)誤。