LeetCode 1. Two Sum
給一個裡面元素為int的陣列，陣列中會有兩個元素加起來等於target，回傳這兩個元素的位置。
範例：
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Input: nums = [3,2,4], target = 6
Output: [1,2]
從集合中，找到那兩個加總為 target 的數字，並回傳它們所在的 index。
method.1 Brute Force
Time complexity:O(n^2)
Space complexity:O(1)
暴力搜索的方法是遍歷所有的兩個數字的組合，然後算其和，這樣雖然節省了空間，但是時間複雜度高。一般來說，為了提高時間的複雜度，需要用空間來換。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
for(int i = 0; i < nums.size(); i++) {
for(int j = i+1; j < nums.size(); j++) {
if(nums[i]+nums[j] == target)
return vector<int>({i,j});
}
}
return {};
}
};
method.2 HashMap(HashTable)
Time complexity:O(n)
Space complexity:O(n)
為了能在時間複雜度為 O(n) 的情況下解此題，直覺上就是只可用一個 for loop
換言之，倘若我們已經在遍歷迴圈在逐一查看 nums 裡每個數字時，應該就要有辦法判斷是否已經有答案存在。
假設現在 for 迴圈正在查看 nums 集合裡的某一個數，好比說 2。對於 2 來說，對應要找的數字為 target - 2（即 9 - 2 = 7）。因此，如果在查看 2 的當下，已經知道 7 存在於 nums 中的話，則代表得到了答案。
因此可做的就是，宣告一個儲存清單，從最一開始，每遇到一個新的數，就先：
Step1.查看對應要找的數字是否已存在於儲存清單中
Step2.如果不存在，就先將該數和其所在的 Index 存起來(未來這個數可能不是、但也可能是答案)。反之，如果對應要找的數字存在於儲存清單中，代表找到答案了！
用target 減去遍歷到的數字，就是另一個需要的數字了，直接在HashMap 中查找其是否存在即可。
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 {};
}
};
備註: end()函數通常用來判斷遍歷是否結束
Ref:
https://clay-atlas.com/us/blog/2022/09/13/leetcode-1-two-sum/
https://k0nze.dev/posts/two-problem-solution-cpp/
https://medium.com/@chingyu.tung/leetcode-%E6%B6%88%E5%8C%96%E9%81%93-two-sum-%E8%A7%A3%E9%A1%8C%E7%AD%86%E8%A8%98-28f07b6dbf2
https://skyyen999.gitbooks.io/-leetcode-with-javascript/content/questions/1md.html
https://deepinout.com/cpp/cpp-tutorials/g_unordered_map-end-function-in-c-stl.html
http://c.biancheng.net/view/7231.html
留言
張貼留言