avatar

leetcode-2:两数相加

描述

给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。

如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外,这两个数都不会以 0 开头。

示例:

1
2
3
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807

思路 1:暴力枚举

暴力枚举方法很简单:两重循环枚举下标 i,j,然后判断nums[i]+nums[j] 是否等于 target

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length; ++i) {
for (int j = i + 1; j < nums.length; ++j) {
if (nums[i] + nums[j] == target) {
return new int[]{i, j};
}
}
}
return null;
}
}

时间复杂度:由于有两重循环,所以复杂度是 O(n^2)

思路 2:哈希表

循环一遍 nums数组,在每步循环中我们做两件事:

  1. 判断target-nums[i]是否在哈希表中;
  2. nums[i]插入哈希表中;

利用 HashMap 作为存储,键为目标值减去当前元素值,索引为值,比如 i = 0 时,此时首先要判断 nums[0] = 2 是否在 map 中,如果不存在,那么插入键值对 key = 9 - 2 = 7, value = 0,之后当 i = 1 时,此时判断 nums[1] = 7 已存在于 map 中,那么取出该 value = 0 作为第一个返回值,当前 i 作为第二个返回值,具体代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public int[] twoSum(int[] nums, int target) {
int len = nums.length;
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < len; ++i) {
final Integer value = map.get(nums[i]);
if (value != null) {
return new int[] { value, i };
}
map.put(target - nums[i], i);
}
return null;
}
}

时间复杂度:由于只扫描一遍,且哈希表的插入和查询操作的复杂度是 O(1),所以总时间复杂度是 O(n)

文章作者: LZ
文章链接: http://lzblog.tech/2020/03/26/leetcode-2-%E4%B8%A4%E6%95%B0%E7%9B%B8%E5%8A%A0/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 LZ Blog
打赏
  • 微信
    微信
  • 支付宝
    支付宝