1.两数之和（C++）

80 阅读 0 评论 53 点赞

我是靠谱客的博主默默钻石，这篇文章主要介绍1.两数之和（C++），现在分享给大家，希望可以做个参考。

题干：
https://leetcode.cn/problems/two-sum/

1、暴力解法
找出所有两两配对，进行判断

复制代码

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) {
    
    if(nums.size() < 2){ throw "array's size is to small!";}
    
        for (int i = 0; i < nums.size(); i++) {
            for (int j = i + 1; j < nums.size(); j++) {
                if (nums[i] + nums[j] == target) {
                    return vector<int>{i, j};
                }
            }
        }
        //没有return答案，抛出异常
        throw "don't find";
    }
};

2、哈希表查找

将问题转化为查找问题，然后使用哈希表，缩短了问题解决的时间。

算法：初始时哈希表为空。遍历数组，对每一个访问到的元素x，在哈希表中查找对应的target-x。找到了则返回答案，没有找到则将该元素x和其下标打包成pair插入到哈希表。

可行性分析：假设原来数组中有一对元素x,y符合要求，那么在我们的算法下，遍历数组。第一次遍历到其中一个元素时(设为x)，由于另一个（y）没有被遍历到，也就不在哈希表中，我们查询哈希表就无法得到答案；但是当我们遍历到另一个元素（y）时，由于另一个配对元素（x）已经在哈希表中，我们一定会搜索哈希表得到答案。所以算法可行。

时间复杂度：主要是遍历数组 O(n)
空间复杂度：哈希表最多有nums.size()-1个元素（默认有答案的条件下），O(n)

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {

		if(nums.size() < 2){ throw "array's size is to small!";}
		
        unordered_map<int, int> hash_map; //用来查找的哈希表，初始为空
        for (int i = 0; i < nums.size(); i++) {
        	//如果在哈希表中找到了，那么直接返回答案
            if ( hash_map.find(target - nums[i]) != hash_map.end()) {
                auto it = hash_map.find(target - nums[i]);
                return vector<int>{i, it->second};
            }
            //如果没有找到，将数组中该元素值作为 key，下标作为 value 插入哈希表
            else {
                hash_map.insert(pair<int, int>{nums[i], i});
            }
        }
		//遍历数组后仍然没有return答案，抛出异常（注意字符串字面量的类型为const char*，捕获异常时不要用string类型）
        throw "don't find";
    }
};