1. Two Sum
- Hardness: \(\color{green}\textsf{Easy}\)
- Ralated Topics:
Array、Hash Table
一、題目
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
Example 1:
- Input: nums = [2,7,11,15], taget = 9
- Output: [0,1]
- Explanation: Because nums[0] + nums[1] == 9, we return [0,1].
Example 2:
- Input: nums = [3,2,4], taget = 6
- Output: [1,2]
Example 3:
- Input: nums = [3,3], taget = 6
- Output: [0,1]
Constraints:
2 <= nums.length <= 10^4-10^9 <= nums[i] <= 10^9-10^9 <= target <= 10^9>- Only one valid answer exists
二、分析
- 可藉由兩個迴圈暴力解求值，其時間複雜度為 \(O(n^2)\)。
- 若我們將已迭代過的值存入 HashMap，接下來我們就只需要找 HashMap 中是否有值與當下的值 nums[i] 相加為 target。因為只迭代一遍，故時間複雜度為 \(O(n)\)。
三、解題
1. HashMap
- Time complexity: \(O(n)\)
- Space complexity: \(O(n)\)
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int> map; // {值, 索引}
int i; // 將 i 宣告在 for-loop 外
for (i = 0; i < nums.size(); i++) {
if (map.find(target - nums[i]) != map.end())
break; // 若找到答案，則退出迴圈
map[nums[i]] = i; // 若沒有符合的答案，將值加入 HashMap
}
return {map[target-nums[i]], i}; // 注意加入 HashMap 的索引值會比當下的 i 值還小
}