秦怀杂货店

General Store

  • 首页
  • 文章归档
  • 标签
  • 分类
  • 关于页面

  • 搜索
随便聊聊 数据结构 小游戏 数据库 Docker Springboot 系统设计 雪花算法 分布式 海量ip 最长回文子串 算法 面试题 线程池 多线程 线程 java学习 布隆过滤器 github 架构设计 docsify Git JVM LeetCode 杂货思考 设计模式 Lambda native isAssignableFrom 反射 剑指Offer mybatis SPI JDBC 编程工具 Java基础 集合

LeetCode【1】-- 两数之和

发表于 2020-12-26 | 分类于 LeetCode | 0 | 阅读次数 293

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

链接:https://leetcode-cn.com/problems/two-sum/

示例:

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

暴力破解:

两层for循环,针对每一个数 n,遍历里面是否有另外一个数为target-n。
时间复杂度为O(n^2),空间复杂度为O(1)。

    public int[] twoSum2(int[] nums, int target) {
        int []result = new int[2];
        for(int i=0;i<nums.length-1;i++){
            for(int j=1;i+j<nums.length;j++){
                if(nums[i]+nums[i+j]==target){
                    result[0]=i;
                    result[1]=i+j;
                }
            }
        }
        return result;
    }

空间换时间

借助hashmap,key为元素的值,value为元素的下标,将数字不断放进hashmap,放之前判断里面是否存在target-num

    public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
        if (nums == null || nums.length == 0) {
            return result;
        }
        Map<Integer, Integer> numSet = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (numSet.containsKey(target - nums[i])) {
                result[0] = numSet.get(target - nums[i]);
                result[1] = i;
                return result;
            } else {
                numSet.put(nums[i], i);
            }
        }
        return result;
    }

复杂度分析:

  • 时间复杂度:O(N),遍历了所有的数。
  • 空间复杂度:O(N),hashMap的大小最大为n。

【作者简介】:
秦怀,公众号【秦怀杂货店】作者,技术之路不在一时,山高水长,纵使缓慢,驰而不息。这个世界希望一切都很快,更快,但是我希望自己能走好每一步,写好每一篇文章,期待和你们一起交流。

此文章仅代表自己(本菜鸟)学习积累记录,或者学习笔记,如有侵权,请联系作者核实删除。人无完人,文章也一样,文笔稚嫩,在下不才,勿喷,如果有错误之处,还望指出,感激不尽~

  • 本文作者: 秦怀杂货店
  • 本文链接: http://aphysia.cn/archives/leetcode01
  • 版权声明: 本博客所有文章除特别声明外,均采用CC BY-NC-SA 3.0 许可协议。转载请注明出处!
# 随便聊聊 # 数据结构 # 小游戏 # 数据库 # Docker # Springboot # 系统设计 # 雪花算法 # 分布式 # 海量ip # 最长回文子串 # 算法 # 面试题 # 线程池 # 多线程 # 线程 # java学习 # 布隆过滤器 # github # 架构设计 # docsify # Git # JVM # LeetCode # 杂货思考 # 设计模式 # Lambda # native # isAssignableFrom # 反射 # 剑指Offer # mybatis # SPI # JDBC # 编程工具 # Java基础 # 集合
剑指Offer【31】-- -- 整数中1出现的次数
Mybatis【11】-- Mybatis Mapper动态代理怎么写?
  • 文章目录
  • 站点概览
秦怀杂货店

秦怀杂货店

纵然缓慢,驰而不息。

145 日志
19 分类
37 标签
Github E-mail
Creative Commons
0%
© 2022 秦怀杂货店
由 Halo 强力驱动
|
主题 - NexT.Pisces v5.1.4