若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。
If you like this post, please click the ads on the blog or buy me a coffee. Thank you very much.
題目原文描述 https://leetcode.com/problems/two-sum/description/
中文描述
指定一個整數陣列 nums 以及一個整數 target，找出在陣列中的兩個整數總合為 target 之索引位置。可以假設每組測試資料剛好只有一組不重複的答案，且一個陣列元素只會使用一次。
範例一：
輸入 nums = [1, 3, 5, 9], target = 8
輸出 [1, 2]
因為 nums[1] + nums[2] = 3 + 5 = 8
範例二：
輸入 nums = [1, 3, 5, 2, 9], target = 10
輸出 [0, 4]
因為 nums[0] + nums[4] = 1 + 9 = 10
解法一：暴力法 Brute Force
使用迴圈找出陣列中任兩個元素 nums[i] + nums[j] 的總和是否等於 target 。
Python Code
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
eleLen = len(nums)
for i in range(eleLen):
for j in range(i + 1, eleLen):
if nums[i] + nums[j] == target:
return [i, j]
C++ Code
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> ret;
for(int i = 0; i < nums.size(); i++) {
for(int j = i + 1; j < nums.size(); j++) {
if( nums[i] + nums[j] == target ) {
ret.push_back(i);
ret.push_back(j);
return ret;
}
}
}
return ret;
}
};
解法二：兩階段查表法 ( two-pass hash table)
第一階段將陣列元素的值當成查詢的鍵值 key，陣列元素的索引當成查詢的值 value。以 nums = [1, 3, 5, 9] 為例，將會建立一個如下的 hash table：
|
key
|
value
|
|
1
|
0
|
|
3
|
1
|
|
5
|
2
|
|
9
|
3
|
然後檢查 target - nums[i] 是否存在此 hask table 的鍵值中。
Python Code
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hashTable = {}
eleLen = len(nums)
# First Pass
for i in range(eleLen):
hashTable[nums[i]] = i
# Second Pass
for i in range(eleLen):
diff = target - nums[i]
if diff in hashTable and hashTable[diff] != i:
return [i, hashTable[diff]]
C++ Code
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> ret;
map<int, int> hashTable;
for(int i = 0; i < nums.size(); i++)
hashTable[nums[i]] = i;
for(int i = 0; i < nums.size(); i++) {
int diff = target - nums[i];
if( hashTable.find(diff) != hashTable.end() && hashTable[diff] != i ) {
ret.push_back(i);
ret.push_back(hashTable[diff]);
return ret;
}
}
return ret;
}
};
解法三：一階段查表法 ( one-pass hash table)
在建立 hash table 時，可以先檢查 target - nums[i] 是否存在此 hash table 的鍵值中，再建立 hash table。
Python Code
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hashTable = {}
eleLen = len(nums)
# One Pass
for i in range(eleLen):
diff = target - nums[i]
if diff in hashTable:
return [i, hashTable[diff]]
hashTable[nums[i]] = i # 先檢查再建立 hash table
C++ Code
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> ret;
map<int, int> hashTable;
for(int i = 0; i < nums.size(); i++) {
int diff = target - nums[i];
if( hashTable.find(diff) != hashTable.end() ) {
ret.push_back(i);
ret.push_back(hashTable[diff]);
return ret;
}
hashTable[nums[i]] = i; // 先檢查再建立 hash table
}
return ret;
}
};
沒有留言:
張貼留言