- 鏈接：https://leetcode-cn.com/problems/two-sum/
- 代碼地址: https://github.com/xvusrmqj/CodeProblems/tree/master/src/main/java/leetcode_cn
題目：
給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)目標(biāo)值 target喳坠，請(qǐng)你在該數(shù)組中找出和為目標(biāo)值的 兩個(gè) 整數(shù)颊埃。
你可以假設(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]
解法：
private 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 sec = target - nums[i];
if (map.containsKey(sec) && map.get(sec) != i) {
return new int[]{i, map.get(sec)};
}
}
throw new IllegalArgumentException("No two sum solution");
}
總結(jié)：
- 這個(gè)題目要知道的就是hash的containsKey(x)是O(1)的時(shí)間復(fù)雜度载弄，所以使用hash表來(lái)做空間換時(shí)間的策略非常常用祝迂。
- 細(xì)節(jié)上注意一個(gè)數(shù)不能用兩遍。這是通過(guò)
map.get(sec) != i來(lái)實(shí)現(xiàn)的缺狠。
