leetcode面試題57. 和為s的兩個數字

文章目錄

• 題目來源
• 解題方法
• • 雙指針
  • 哈希表

題目來源

解題方法

雙指針

思路：

為什麼想到用雙指針呢，其中一個比較重要的提示就是遞增數組，首先我們可以先用兩個變量i,j存儲頭尾的索引，接着判斷nums[i]+nums[j]是否等于目标target，若等于，則直接傳回即可，若小于，說明我們需要更大的左部，是以可以選擇令i++，若大于，說明我們需要更小的左部，是以可以選擇令j- -，循環結束條件即為i==j

附上代碼

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

哈希表

思路：

可以将題意了解為對于一個數a，(target-a)是否在數組中出現

于是可以先周遊一遍，将數組中的每個數存在hash表中，接着再周遊一遍看看能不能取到對應的數字即可完成

附上代碼

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