两数之和Ⅰ+Ⅱ

两数之和Ⅰ

题目：给定一个整数数组 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};
    }
};