題目
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, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
翻譯
給定一個整數(shù)數(shù)組师骗，找出其中兩個數(shù)滿足相加等于你指定的目標(biāo)數(shù)字。
每個輸入只有一個唯一解华匾。相同的元素不能用兩次胀葱。
解題思路
那么本題呢雙重循環(huán)的方法在這里就不說了鲜屏。主要展示一下借助HashMap實現(xiàn)吱抚。以及要考慮的問題。
思路還是比較簡單的豁延。首先我們把所有元素放到map中昙篙。key為元素本身。value為元素在數(shù)組中的索引值诱咏。放到map中是因為方便查找元素的位置苔可。同時哈希表查找元素的時間復(fù)雜度是O（1）級別的。
然后再遍歷一邊數(shù)組袋狞。查找map中對應(yīng)的那個元素焚辅。
代碼如下
// 1. Two Sum
// https://leetcode.com/problems/two-sum/description/
// 時間復(fù)雜度：O(n)
// 空間復(fù)雜度：O(n)
public class Solution2 {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> record = new HashMap<Integer, Integer>();
for(int i = 0 ; i < nums.length ; i ++)
record.put(nums[i], i);
for(int i = 0 ; i < nums.length; i ++){
if(record.containsKey(target - nums[i]))
if(record.get(target - nums[i]) != i){ //不能是同一個的元素相加等于目標(biāo)值
int[] res = {i, record.get(target - nums[i])};
return res;
}
}
throw new IllegalStateException("the input has no solution");
}
}
題到這里就結(jié)束了嗎映屋？那么有沒有想過這么一種可能。這個數(shù)組中假如有兩個值都為a的元素同蜻。那么我們將數(shù)組中的元素放到map中時棚点。后面的那個a就將前面那個a覆蓋了。a對應(yīng)的value值為后面那個a的索引湾蔓。如圖：
如果此題的目標(biāo)值剛好是2a瘫析。就是這兩個a相加呢？其實這種情況也沒有關(guān)系默责。想想當(dāng)我們第二次遍歷數(shù)組時颁股。首先肯定遍歷到的是數(shù)組中的第一個a。此時我們查找map時傻丝。找到的另一個值也是a甘有。而map中的這個a剛好使我們數(shù)組中的第二個a。因為map中第一個a已被第二個覆蓋掉了葡缰。所以取當(dāng)前數(shù)組中的a的索引亏掀。同時取map中a的索引。就剛好是我們要的答案泛释。
關(guān)注我免費下載CSDN
關(guān)注公眾號哦
