当前位置:   article > 正文

leetcode刷题笔记1. 两数之和_leetcode刷题系列】1.两数之和

leetcode刷题系列】1.两数之和

(https://leetcode.cn/problems/two-sum/)

1.题目描述:

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那两个整数,并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

2.解题思路:

第一个想到的就是暴力遍历,从第一个开始一个个计算数据的和,时间复杂度O(N²),代码如下:

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

时间复杂度实在有点高,考虑一下别的方式。

看了一些资料,还是要用哈希表,使用hashmap保存(int ,int)这个键值对,前面的值是输入的数字,后面的值是下标。

只需要遍历一遍数组,在遍历每个元素的时候通过find()函数寻找与其匹配的值。这样只需要遍历一遍数组就可以得到结果,时间复杂度O(N)。代码如下:

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

3.总结

hashmap的效率很高,对比两次代码的速度
在这里插入图片描述

可以看出hashmap效率上碾压暴力法。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/在线问答5/article/detail/972773
推荐阅读
相关标签
  

闽ICP备14008679号