Last Updated on 2021-12-05 by Clay
題目
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:
Input: nums = [2,7,11,15], target = 9 Output: [0,1] Output: Because nums[0] + nums[1] == 9, we return [0, 1].
簡單來講，我們有一組整數數列 nums 和一個目標值 target，我們要找到數列中兩個整數相加等於 target，並返回相加等於 target 的兩個數值的索引（Index）。
比方說 index=0 的數值和 index=3 的數值相加等於 target，我們就需要返回 (0, 3)。
解題思路
這題可說是 LeetCode 最經典的題目之一 —— 因為這是編號上的第一題。
Brute Force
| Time complexity | O(n^2) |
| Space complexity | O(1) |
解題時第一感想到的方法，大部分都是直接使用兩層 for 迴圈來遍歷所有組合。不過這種方法比較費時。
C++ 範例程式碼
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
// Find
for (int i=0; i<nums.size(); ++i) {
for (int j=i+1; j<nums.size(); ++j) {
if (nums[i] + nums[j] == target) {
return {i, j};
}
}
}
return {};
}
};Python 範例程式碼
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)):
for j in range(i+1, len(nums)):
if nums[i] + nums[j] == target:
return (i, j)HashMap
| Time complexity | O(n) |
| Space complexity | O(n) |
另外一個優化過的解決方法，就是開個 hash table 或是新的陣列，依序讀出 nums 數列中的數值。如果當前讀取的數值不在 hash table 或陣列中，則存入當前數值還差距 target 多少；如果當前數值剛好等於之前存入的某個數值差距，則剛好就是那個數值差距的值與當前數值為標準答案。
C++ 範例程式碼
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> losses;
for(int i=0; i<nums.size(); i++) {
if (losses.find(nums[i]) != losses.end()) {
return {losses[nums[i]], i};
}
else {
losses[target-nums[i]] = i;
}
}
return {};
}
}; Python 範例程式碼
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
losses = dict()
for i in range(len(nums)):
if nums[i] in losses:
return (losses[nums[i]], i)
else:
losses[target-nums[i]] = i
如此一來，幾乎便是在迴圈只跑一輪的情況下解出答案了。