前言
这道题是Leetcode的第一题，也是经典题目之一，几乎所有刷题网站的第一题都是“两数之和”，只是Leetcode这道题不一样。
在这篇博客中，我们介绍了两种解法：
| 暴力算法 | 哈希表算法 |
|---|---|
| \(\mathcal{O}(n^2)\) | \(\mathcal{O}(n)\) |
题目描述
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1]
示例2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例2：
输入：nums = [3,3], target = 6
输出：[0,1]
提示
- \(2 \leq nums.length \leq 10^4\)
- \(-10^9 \leq nums[i] \leq 10^9\)
- \(-10^9 \leq target \leq 10^9\)
- 只会存在一个有效答案
题目分析
由于题目描述得比较清晰，所以不用过多分析。需要注意的是，题目已经说明每种输入只对应一个答案，说明我们不用考虑有多个答案的情况。
暴力算法
阅读完题目之后，首先能想到的解法就是确定一个值 \(nums[i] , 0 \leq i \leq nums.length-1\) ，在剩余的序列中找到 \(target-nums[i]\) 。
解题代码
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
for (int i = 0 ; i < nums.size() - 1 ; i ++) {
/* j 从 i+1 开始，是因为两个下标不能相同，题目有说明*/
for (int j = i + 1 ; j < nums.size() ; j++) {
if ( nums[j] == target - nums[i]) {
return {i , j};
}
}
}
return {};
}
};
复杂度分析
设 \(nums\) 的长度为 \(n\) ，可以得到等式
\[\begin{equation}\begin{aligned} Complex &= \underbrace{(n-1) + (n-2) + (n-3) +\cdots + 1}_{n-1} = \frac{[1 + (n-1)]\times(n-1)}{2} \\ &= \frac{n^2-n}{2} = \frac{1}{2}n^2 -\frac{1}{2}n. \end{aligned}\end{equation} \]因此\(\mathcal{O}(Complex) = \mathcal{O}(\frac{1}{2}n^2 -\frac{1}{2}n) = \mathcal{O}(n^2)\)
我们在刚开始刷题的时候，可以先试着自己写出暴力算法，然后分析一下时间复杂度，再尝试其他解题方法。
由暴力算法可以得知，主要的时间消耗是在寻找 \(target-nums[i]\) 上，如果能降低寻找 \(target-nums[i]\) 的时间，就能实现一个时间复杂度小于 \(\mathcal{O}(n^2)\) 的算法。
因此我们考虑用 哈希表 来解决这一问题 。
哈希表算法
最开始接触到哈希表思想是从桶排序算法，它的典型思想是以空间换时间，哈希表的时间复杂度为\(\mathcal{O}(1)\) 。
我们可以将数组分为两部分，如下图：
解题代码
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int> idx;
for (int j = 0 ; j < nums.size() ; j++) {
auto it = idx.find(target-nums[j]);
if ( it != idx.end()) {
return { it->second , j};
}
idx[nums[j]] = j;
}
return {};
}
};
复杂度分析
设 \(nums\) 的长度为 \(n\) ，可以得到时间复杂度等式
\[\begin{equation}\begin{aligned} \mathcal{O}(Complex) &= \mathcal{O}(\text{哈希查找}) + \mathcal{O}(\text{遍历})\\ &=\mathcal{O}(1) + \mathcal{O}(n) = \mathcal{O}(n+1)\\ &= \mathcal{O}(n). \end{aligned}\end{equation} \]空间复杂度为 \(\mathcal{O}(n)\).
标签：target,nums,复杂度,leq,哈希,mathcal,LeetCode,两数 From： https://www.cnblogs.com/whtmomo/p/18344917