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].
UPDATE (2016/2/13):
The return format had been changed to zero-based indices. Please read the above updated description carefully.
給定一個整數(shù)數(shù)組和一個目標(biāo)數(shù)target祟滴，返回和恰好等于target的兩個元素的序號，這里假定每個輸入都有恰好唯一解勾邦。
思路
這類問題基本的思路是要順序掃描數(shù)組烈掠，對于當(dāng)前元素nums[i]，掃描數(shù)組中是否存在元素target-nums[i]致讥，主要通過兩種方式查找：
- 排序數(shù)組岩齿，二分查找虫碉，但此題目需要返回解元素的序號呛哟，因而此種方式不適用
- 構(gòu)建一個哈希map叠荠，用于保存數(shù)組元素以及它們的序號，此方法遍歷時間O(n)扫责，尋找時間O(1)榛鼎，總時間復(fù)雜度O(n)，空間復(fù)雜度O(n)公给。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int> hash;
vector<int> result;
for(int i=0;i!=nums.size();i++){
int numsToFind = target-nums[i];
if(hash.find(numsToFind)!=hash.end()){
result.push_back(hash[numsToFind]);
result.push_back(i);
return result;
}
hash[nums[i]]=i;
}
return result;
}
};
public class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer,Integer> map=new HashMap<>();
for(int i=0;i<nums.length;i++){
int numToFind=target-nums[i];
if(map.containsKey(numToFind)) return new int[]{ map.get(numToFind),i};
map.put(nums[i],i);
}
throw new IllegalArgumentException("No two sum solution");
}
}
