Long

欢迎来到Long的博客站点

第167题: two_sum_II

题目描述

给定一个已按照升序排列 的有序数组,找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2,其中 index1 必须小于 index2。
说明:
返回的下标值(index1 和 index2)不是从零开始的。
你可以假设每个输入只对应唯一的答案,而且你不可以重复使用相同的元素。

示例:
输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

解法

从题目描述中可以知道的是,这题和第一题是非常相似的,只不过第一题中的输入数组是一个有序数组,而这里的输入数组是一个无序数组,回忆一下,第一题中的较好解法就是将数组中的数据放入map中,利用map中查找元素的时间复杂度为O(1)的特性,其实就是空间换时间,降低时间复杂度;这里其实也是也可以采用这种手法,但是这样做的话,题目给出的有序就失去了意义,所以我们这里就需要利用题目中的有序。

解法一

暴力破解,时间复杂度为O(n^2), 空间复杂度为O(1)

#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::string;
using std::vector;

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

int main(void)
{
    vector<int> vec{2, 7, 11, 15};
    Solution so;
    vector<int> ret = so.twoSum(vec, 9);
    for (auto elem : ret)
        cout << elem << " ";
    cout << endl;

    return 0;
}
解法二

解法二就是和第一题的解法一样,建立underorder map来求解

#include <iostream>
#include <vector>
#include <unordered_map>

using std::cout;
using std::endl;
using std::vector;
using std::unordered_map;           //此数据结构利用的是hash来存储元素的,查找一个元素的时间复杂度为O(1)

class Solution 
{
public:
    vector<int> twoSum(vector<int> & numbers, int target) 
    {
        //建立hash map
        unordered_map<int, int> index_numbers;
        for (int i = 0; i < numbers.size(); ++i)
        {
            index_numbers[numbers[i]] = i;
        }

        for (int i = 0; i < numbers.size(); ++i)
        {
            auto iter = index_numbers.find(target - numbers[i]);
            if (iter != index_numbers.end() && iter->second != i)
                return vector<int>{i + 1, iter->second + 1};
        }
    }
};

int main(void)
{
    vector<int> vec{2, 7, 11, 15};
    Solution so;
    vector<int> ret = so.twoSum(vec, 9);
    for (auto elem : ret)
        cout << elem << " ";
    cout << endl;

    return 0;
}
解法三

双指针法,解法一和解法二均没有利用上题目中的有序性质,虽然解法二的时间复杂度为O(n), 但是空间复杂度为O(n),利用了map来存储数组中的数据,从而降低时间复杂度,这里我们利用输入数组的有序性质,定义两个索引(i和j),i指向数组的头部,j指向数组的尾部,如果两者相加不等于目标值,那么两者的和妖魔大于目标值,要么小于目标值,但是题目中说了,数组中一定存在满足条件的下标,所以我们要做的就是寻找而已,如果两者之和大于目标值,表示j所指向的那个值太大了,需要缩小;如果两者之和小于目标值,说明i所指向的值太小了,需要扩大,这时执行i++;重复上述步骤,知道找出这两个下标。

#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::string;
using std::vector;

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

int main(void)
{
    vector<int> vec{2, 7, 11, 15};
    Solution so;
    vector<int> ret = so.twoSum(vec, 9);
    for (auto elem : ret)
        cout << elem << " ";
    cout << endl;

    return 0;
}
点赞

发表评论

电子邮件地址不会被公开。