前言
秋招的结束, 面试了大大小小的公司, 最大的问题在于算法上. 所以打算坚持在 leetcode 打卡, 看看到底能不能行, 如果你想见证, 那我来开车, 你坐稳, 一起走向更好的远方. 2020=1024+996, 准备好了?
一 题目
给定一个整数数组 nums 和一个目标值 target, 请你在该数组中找出和为目标值的那 两个 整数, 并返回他们的数组下标.
你可以假设每种输入只会对应一个答案. 但是, 你不能重复利用这个数组中同样的元素.
1 leetcode 链接
https://leetcode-cn.com/problems/two-sum/
示例
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
2 思路 1--- 暴力解法
我们需要在一个数组 nums 中寻找两个数, 然后呢这个两个数之和需要等于目标的值. ok, 我的外层循环从第一个数开始遍历, 内层循环从第二个数遍历, 如果这两个数和等于目标值, 我就返回下标, 问题来了, 我要返回下标, 所以需要先暂存起来才方便, 而且返回的类型也需要确定. 在这里, 我的返回类型为 vector, 然后可以直接使用 {i,j} 的方式来存储下标. 好了, 代码呈上!
- class Solution {
- public:
- vector<int> twoSum(vector<int>& nums, int target) {
- //int result[]={0.1};
- int i= 0;
- int j=0;
- for(i;i<nums.size()-1;i++)
- {
- for(j=i+1;j<nums.size();j++)
- {
- if(nums[i]+nums[j]==target)
- {
- return {i,j};
- }
- }
- }
- return {i,j};
- }
- };
3 思路 2--- 上 hash
首先咋们想想 hash 是个什么玩意儿, 存在既有意义嘛. 从定义来说是根据关键码值 (Key value) 而直接进行访问的数据结构. 也就是说, 它通过把关键码值映射到表中一个位置来访问记录, 以加快查找的速度. 那我们看看下图, 看 NBA 的童鞋应该知道下面的几位大佬, 他们也有对应的外号, 这样就形成了 key value 的 hash 结构.
ok, 那有些小伙伴有想法了, 貌似很多明星都有好几个外号呀, 比如哈登还有大胡子的外号怎么办, 这里咱们可以使用拉链法的方式如下图.
好了, 我们大概知道 hash 的一点点基本原理, 然后这个题目怎么使用 hash 来解决呢?
确定返回值类型为 vector
在 c++ 中类似 hash 这种 key,value 的容器有 map,unorder_map 等, 我们选择 unordered_map.
循环遍历数组, 每得到一个元素 A, 就去 hash 表中寻找是否存在 target-A, 注意, hash 查找的时间复杂度为 O(1)
- class Solution {
- public:
- vector<int> twoSum(vector<int>& nums, int target) {
- vector<int> res;
- unordered_map<int, int> hash_map;// 由于 unorder_map 速度要比 map 快所以选择无序哈希表
- for(int i=0; i <nums.size();++i){
- int another = target - nums[i];
- if(hash_map.count(another)){
- res = vector<int>({hash_map[another], i});
- return res;
- }
- hash_map[nums[i]] = i;
- }
- return res;
- }
- };
4 总结
文中使用了两种方式来解决这个问题, 第一种为复杂度较高的暴力解答, 第二种使用 hash 的方式来解答, 其中了解 hash 的基本原理, 后续会对 hash 进行详细的阐述以及应用场景. 至此, 咱们想想如何解决三数之和的问题呢?
5 结尾
希望读者和咱一起一步一个脚印去把基础知识打牢固. 如果读者发现有什么错误或者不太好的地方, 欢迎私我, 我会及时修改.
[leetcode 数组系列]1 两数之和
来源: http://www.bubuko.com/infodetail-3361306.html