[数组][哈希表]leetcode167：两数之和Ⅱ-输入有序数组(easy)

77 阅读 0 评论 51 点赞

我是靠谱客的博主缥缈洋葱，这篇文章主要介绍[数组][哈希表]leetcode167：两数之和Ⅱ-输入有序数组(easy)，现在分享给大家，希望可以做个参考。

题目：
在这里插入图片描述
题解1：哈希表

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        /*解法1：哈希表*/ 
        unordered_map<int,int> record;//元素->下标
        for(int i=0;i<numbers.size();++i)
            record[numbers[i]]=i+1;
        for(int i=0;i<numbers.size();++i)
        {
           if(record.count(target-numbers[i]))
               return vector<int> {i+1,record[target-numbers[i]]};
        }
    return {};
    }
};

题解2：双指针

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
            //解法2：双指针,注意本题是有序数组
        int i=0,j=numbers.size()-1;
        while(i<j)
        {
            int sum=numbers[i]+numbers[j];
            if(sum==target)return {i+1,j+1};
            else if(sum>target)j--;//sum比target大，j左移一格
            else i++;//sum比target小，i右移一格
        }
        return {};
    }
};