兩數之和Ⅰ+Ⅱ

兩數之和Ⅰ

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

你可以假設每種輸入隻會對應一個答案。但是，數組中同一個元素不能使用兩遍。

示例:

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

因為 nums[0] + nums[1] = 2 + 7 = 9

是以傳回 [0, 1]

解題思路

這道題可以采用哈希表來解題。我們首先定義一個unordered_map<int,int>hashtable，然後從頭開始周遊整個數組，在周遊的同時，從hashtable中查找是否存在（target-nums[i]），若存在則直接傳回{it->second,i}，若不存在則将數組中目前值和它的下标加入到hashtable中。

代碼展示

代碼如下：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int>hashtable;
        for(int i=0;i<nums.size();i++)
        {
            auto it=hashtable.find(target-nums[i]);
            if(it!=hashtable.end())
            {
                return {it->second,i};
            }
            hashtable[nums[i]]=i;
        }
        return {};
    }
};
           

兩數之和Ⅱ

題目：給定一個已按照升序排列 的有序數組，找到兩個數使得它們相加之和等于目标數。

函數應該傳回這兩個下标值 index1 和 index2，其中 index1 必須小于 index2。

說明:

傳回的下标值（index1 和 index2）不是從零開始的。

你可以假設每個輸入隻對應唯一的答案，而且你不可以重複使用相同的元素。

示例:

輸入: numbers = [2, 7, 11, 15], target = 9

輸出: [1,2]

解釋: 2 與 7 之和等于目标數 9 。是以 index1 = 1, index2 = 2 。

解題思路

這道題可以使用 兩數之和Ⅰ 的解法，借助哈希表使用 O(n)的時間複雜度和 O(n) 的空間複雜度求解。但是這種解法都是針對無序數組的，沒有利用到輸入數組有序的性質。利用輸入數組有序的性質，我們可以使用雙指針法來獲得更優解。

算法流程：

初始時兩個指針分别指向第一個元素位置和最後一個元素的位置。每次計算兩個指針指向的兩個元素之和，并和目标值比較。

1. 如果兩個元素之和等于目标值，則發現了唯一解。
2. 如果兩個元素之和小于目标值，則将左側指針右移一位。
3. 如果兩個元素之和大于目标值，則将右側指針左移一位。
4. 移動指針之後，重複上述操作，直到找到答案。

代碼展示

代碼如下：

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