题目

1. 两数之和

答案

方法一:

暴力求解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        for(int i=0;i<nums.size();i++)
        {
            for(int j=i+1;j<nums.size();j++)
            {
                if(nums[i]+nums[j]==target)
                {
                    return {i,j};
                }

            }
        }
        return {};
    }
};

方法二：

哈希表

哈希表（hash table），又称散列表，类似于python里的字典，它通过建立键 key 与值 value 之间的映射，实现高效的元素查询。具体而言，我们向哈希表中输入一个键 key ，则可以在 𝑂(1) 时间内获取对应的值 value 。

image-20240709132800705

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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 index = hashtable.find(target-nums[i]);
            if(index != hashtable.end())
            {   
                //第二个值
                return {index->second,i};
            }
            hashtable[nums[i]] = i;
        }
        return {};
    }
};

__END__