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效率上碾压暴力法。