侧边栏壁纸
博主头像
Wyatt博主等级

Done is better than perfect!

  • 累计撰写 103 篇文章
  • 累计创建 31 个标签
  • 累计收到 7 条评论

#1-两数之和

Wyatt
2021-01-29 / 0 评论 / 0 点赞 / 221 阅读 / 1,164 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2021-06-23,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

一. 描述

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 的那 两个 整数,并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。
你可以按任意顺序返回答案。

二. 思路

2.1 分析

本题有2中方法:暴力遍历和哈希表。但是暴力遍历的时间复杂度为O(N2),不是最优解,暂不考虑。

  • 哈希表的查询时间复杂度为 O(1),并且当前空间复杂度为O(N)
  • 遍历数组 nums,i 为当前下标,每个值都判断map中是否存在 target-nums[i] 的 key 值
  • 如果存在则找到了两个值,如果不存在则将当前的 (nums[i],i) 存入 map 中,继续遍历直到找到为止

2.2 步骤

  1. 创建一个哈希O(N)的哈希表,长度为nums.length-1
  2. 遍历数组,对期望值(target - nums[i])进行哈希表查询
    • 如果存在,则返回该值
    • 如果不存在,则向哈希表插入该值
  3. 一直无结果,则返回0

三.代码

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>(nums.length - 1);
        for (int i = 0; i < nums.length; i++) {
            int x = target - nums[i];
	    //此处的意义就是将O(N<sup>2</sup>)降为O(1)。
            if (map.containsKey(x)) {
                return new int[]{map.get(x).intValue(),i};
            } else {
                map.put(nums[i], i);
            }
        }
        return new int[0];
    }
}

四.总结

  1. 本题专注于空间换时间,降低时间复杂度,这是一种升维思想
  2. 灵活确定空间长度,减少HashMap自动创建带来的空间浪费
  3. 将具体树值作为Key,并将下标存为Value,方便管理

执行结果
image.png

0

评论区