LeedCode_初級算法_數組_兩數之和(Two Sum)_9

9. 兩數之和

給定一個整數數組 nums 和一個目标值 target，請你在該數組中找出和為目标值的那 兩個 整數，并傳回他們的數組下标。

你可以假設每種輸入隻會對應一個答案。但是，你不能重複利用這個數組中同樣的元素。

示例:

給定 nums = [2, 7, 11, 15], target = 9

因為 nums[0] + nums[1] = 2 + 7 = 9
是以傳回 [0, 1]
           

解法1

暴力求解，周遊數組，找出兩個元素相加為target的兩個元素的位置。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result;
        for(int i=0;i<nums.size()-1;i++){
            for(int j=i+1;j<nums.size();j++){
                if(nums[i]+nums[j]==target){
                    result.push_back(i);
                    result.push_back(j);
                    return result;
                }
            }
        }
        return result;
    }
};
           

時間複雜度：O(n^2)

空間複雜度：1

29 / 29 個通過測試用例

執行用時：220 ms

解法2

使用hash表，在hash表中進行查找時間是O(1)的時間複雜度。建立一個map<int,int>對象，将nums的值作為key,nums的下标為value。周遊數組，然後查找target-nums[i]這個值。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result;
        map<int,int> hash_val;
        int find_val;
        for(int i=0;i<nums.size();i++){
            hash_val[nums[i]]=i;
        }
        for(int i=0;i<nums.size();i++){
            find_val=target-nums[i];
            if(hash_val.find(find_val)!=hash_val.end()){
                if(hash_val[find_val]!=i){
                    result.push_back(i);
                    result.push_back(hash_val[find_val]);
                    return result;
                }
            }
        }
        return result;
    }
};
           

時間複雜度：O(n)。 建立hash映射：n。尋找：n。

空間複雜度：O(n)。 建立hash映射：n。

29 / 29 個通過測試用例

執行用時：36 ms