刷一刷 LeetCode 算法题,尝试将刷过题都记录一下。每题尽量用 C 和 Python 来写。
标题 | 两数之和 |
---|---|
序号 | NO.1 |
难度 | 简单 |
标签 | 数组 哈希表 |
1. 题目
给定一个整数数组 nums
和一个整数目标值 target
,请你在该数组中找出 和为目标值 target
的那两个整数,并返回它们的数组下标。你可以假设每种输入只会对应一个答案
。但是,数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1:
输入:nums = [2,7,11,15], target = 9 |
示例 2:
输入:nums = [3,2,4], target = 6 |
示例 3:
输入:nums = [3,3], target = 6 |
提示:
- 2 <= nums.length <= 109
- -109 <= nums[i] <= 109
- -109 <= target <= 109
- 只会存在一个有效答案
进阶:你可以想出一个时间复杂度小于 O (n2) 的算法吗?
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/two-sum/
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
2. 代码
方法一:暴力求解
LeetCode 第一题,还是比较简单的,两层嵌套遍历数组即可,注意两次遍历不能为同一个数,另外注意 i+j=j+i
,所以第二次只需要遍历比第一次大的数即可,这样能节省一半的时间。
时间复杂度 O (n2)
空间复杂度 O (1)
执行用时:3324ms
内存消耗:15.6MB
class Solution: |
- 执行用时:96ms
- 内存消耗:6MB
1 | /** |
方法二:哈希映射
利用哈希表将每个数 x
与下标 i
对应起来,组成键值对 key:x
, value:i
;
然后遍历列表,查找 target-y 是否存在于哈希表中,若存在即查找成功。
时间复杂度 O (n)
空间复杂度 O (n)
执行用时:24ms
内存消耗:16MB
1 | class Solution: |
enumerate()
函数用于将一个可遍历的数据对象 (如列表、元组或字符串) 组合为一个索引序列,同时列出数据和数据下标,一般用在 for 循环当中。
可以将列表转为类似字典形式,下标与数据一一对应。
哈希映射法将时间复杂度从 O (n2) 降到了 O (n),但空间复杂度也从 O (1) 上升到了 O (n),是典型的以空间换时间思想。
对比两个 Python 代码,暴力求解法需要运行 3s,而哈希映射法只用了 24ms,而内存消耗也没有增加,性能远超暴力求解法。