Two Sum —— leet code 每天一練
摘要：
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 wou...
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 sameelement twice.
Example:
Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].
第一種解法，使用 Recursion：
// typescript
var twoSum = function(nums: number[], target: number) {
const result: number[] = [];
for (let i = 0; i < nums.length; ++i) {
const diff = target - nums[i];
for (let j = nums.length; j > i; --j) {
if (diff === nums[j]) {
result.push(i);
result.push(j);
}
}
}
return result;
};
執行情況:
Runtime: 328 ms, faster than 5.07% of JavaScript online submissions for Two Sum. Memory Usage: 34.8 MB, less than 44.49% of JavaScript online submissions for Two Sum.
複雜度分析：
-
時間複雜度為：O(n^2). 對於每個元素而言，我們通過迴圈遍歷剩餘得的陣列來查詢它的補數，這花費了 O(n) 的時間複雜度，因此，這個時間複雜度為 O(n^2).
-
空間複雜度：O(1).
第二種解法，使用 HashTable
// typescript
var twoSum = function(nums: number[], target: number) {
const map: {[key: number]: number} = {};
for (let i = 0; i < nums.length; ++i) {
if (map[target - nums[i]] !== undefined) {
return [map[target - nums[i]], i];
}
map[nums[i]] = i;
}
};
執行情況:
Runtime: 60 ms, faster than 91.05% of JavaScript online submissions for Two Sum. Memory Usage: 34.4 MB, less than 83.16% of JavaScript online submissions for Two Sum.
複雜度分析：
-
時間複雜度為：O(n). 我們只遍歷了一次陣列包含的 n 個元素. 每次查詢雜湊表所花費得時間為 O(1).
-
空間複雜度：O(n). 額外空間得大小需要依賴於元素的儲存數量，最大儲存量為 n 個元素，最小為 1.
額外提供 C++ 解法：
C++
class Solution
{
public:
static std::vector<int> twoSum(std::vector<int> &nums, int target)
{
auto table = new std::map<int, int>();
for (int i = 0; i < nums.size(); ++i)
{
auto iterator = (*table).find(target - nums[i]);
if (iterator != table->end())
{
return {(*table)[target - nums[i]], i};
}
(*table)[nums[i]] = i;
}
return {};
}
};
執行情況:
Runtime: 16 ms, faster than 58.40% of C++ online submissions for Two Sum. Memory Usage: 10 MB, less than 56.09% of C++ online submissions for Two Sum.
計算型果然還是 C++ 比較快，看上去比 JS 快了 6~7 倍…