从零打卡leetcode之day 1--两数之和

前言

深知自己在算法方面上很菜,于是打算通过打卡的方式,逼自己一把。每天在leetcode上打卡,并且把自己的想法分享出来。这将是一段漫长而又艰辛的旅程。如果你也想和我一起走上一条充满艰辛的航路,那么,别犹豫了,上车吧,一起学习一起探讨。


从零打卡leetcode之day 1

题目描述:
给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。

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

看到这道题的第一想法,暴力暴力,能用暴力解决的事情不要和我谈其他。

于是,两个for循环噼里啪啦。

    //方法一:简单暴力,两个for循环搞定
    public int[] twoSum1(int[] nums, int target) {     
       int[] temp = new int[2];//用来存要找的数的下标
        for(int i = 0; i < nums.length; i++){         
          for(int j = i + 1; j < nums.length; j++){            
              if(nums[i] + nums[j] == target){
                    temp[0] = i;
                    temp[1] = j;              
                    return temp;
                }
            }
        }   
                    
          return null;
    }

不过心里才两个循环时间复杂度可是n的平方,心想肯定得超时,不过还是大胆提交一下提交,呵呵,居然通过了。。。。

我猜这可能是第一道题的原因,让我们开心一下。不过排名你懂的。

不过居然要刷题,要学习算法,那么肯定是不能满足于「第一想法」的,必须得找出我们自己能接受的最优解。

于是我想到了用空间换时间,就是我们可以用哈希表映射的方法,先把数组里所有元素的值作为key,下标作为value存进hashmap里,我们知道从hashmap里查找元素的时间复杂度近似常数,即O(1)。然后我们可以用一个for循环来遍历数组,遍历的过程中一边查找另一个数是否在hashMap里,例如a = nums[i],然后查找b = targert - a是否在hashMap里,如果在,则证明a,b便是要找的数,否则继续查找。代码下:

public int[] twoSum2(int[] nums, int target){    
        int[] temp = new int[2];
        Map<Integer,Integer> map = new HashMap<>();     
       for(int i = 0; i < nums.length; i++){
            map.put(nums[i], i);
        }        //遍历查找
        for(int i = 0; i < nums.length; i++){       
            int a = nums[i];          
              if(map.containsKey(target - a)){
                temp[0] = i;
                temp[1] = map.get(target - a);   
                return temp;
            }
        }     
                   return null;
    }

不过,不知道大家发现问题了没有,题目里只是说会有唯一解,并且一个元素只能用一次,但并没有说,不能两个元素的值相同,也就是说,数组如果有元素的值相同的话,存进hashMap会出现冲突的情况。所以,这样先把数组的所有元素存进hashMap的做法是不严谨的。

我们来分析一下处理方法:

出现这个问题的本质原因是因为我们要找的那两个数刚好相等,导致我们当存进哈希表的时候出现了丢失的情况。如何解决?

上面说了,问题的原因是这两个我们要的数刚好相等,并且我们从一开始就想把他们两个硬塞进哈希表里,导致一山容不了二虎。其实,我们可以换一种想法啊,我们可以一边遍历查找一边把数放进哈希表里啊。 先看代码:

public int[] twoSum3(int[] nums, int target){   
     int[] temp = new int[2];
        Map<Integer,Integer> map = new HashMap<>(); //遍历查找
        for(int i = 0; i < nums.length; i++){       
          int a = nums[i];           
           if(map.containsKey(target - a)){
                temp[0] = map.get(target - a);
                temp[1] = i;              
                return temp;
            }else {//如果找不到则存进去
                map.put(nums[i], i);
            }
        }    
         return null;          
    }

就是取出数a=nums[i],先判断b=target-a在不在哈希表里,如果在,那么a和b就是要找的值了,如果不在,就把a放进哈希表了。

这样,就不会出现上面那种情况的冲突了,因为两个我们要找的数,只有一个会放在哈希表里。拉你进群。 在公众号右下方有我的微信二维码。


原文发布于微信公众号 - 苦逼的码农(di201805)

原文发表时间:2018-08-04

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java技术栈

跟我学 Java 8 新特性之 Stream 流(五)映射

经过了前面四篇文章的学习,相信大家对Stream流已经是相当的熟悉了,同时也掌握了一些高级功能了,如果你之前有阅读过集合框架的基石 Collection 接口,...

9920
来自专栏数说工作室

class 类—老司机的必修课 | 统计师的Python日记 第11课

本文是【统计师的Python日记】第11天的日记 回顾一下: 第1天学习了Python的基本页面、操作,以及几种主要的容器类型。 第2天学习了python的函...

382100
来自专栏WeaponZhi

轻松初探 Python 篇(五)—dict 和 set 知识汇总

这是「AI 学习之路」的第 5 篇,「Python 学习」的第 5 篇 dict dict 是 Python 内置的字典类型,熟悉 Java 的同学可以把它类比...

31890
来自专栏Python区块链

人工智能实现程序员“防”BOSS?刷脸就发短信,8行代码人脸报警

如今一个攻城狮就能搞定人脸的深度进修算法,这要多感激打动国外开源框架,虽然达不到旷世face++和诸多人脸公司的深度,可是实际应用已经没有太大压力。下图就是te...

479120
来自专栏小詹同学

【记录帖】从零打卡刷Leetcode——No.007

小詹此记录贴的读者越来越少了,也许是小詹总结的不够好欢迎留言区提出宝贵的意见!也欢迎和小詹一起定期刷leetcode,每周一和周五更新一题,每一题都吃透,欢迎一...

14330
来自专栏xingoo, 一个梦想做发明家的程序员

Java程序员的日常—— 基于类的策略模式、List<?>与List、泛型编译警告、同比和环比

早晨起得太早,昨晚睡得太晚,一天都迷迷糊糊的。中午虽然睡了半个小时,可是依然没有缓过来。整个下午都在混沌中....不过今天下载了一款手游——《剑侠情缘》,感觉...

19670
来自专栏AI派

Numpy 修炼之道 (13)—— 将python函数向量化

想要实现将python函数向量化,Numpy中的vectorize 和frompyfunc函数都可以满足要求。

46570
来自专栏算法channel

程序员必知的算法和数据结构:2500字性能总结

以下5个步骤总结了此方法,依次为如下,我们设计的实验必须是可以重现的,我们形成的假设必须是具有真伪的。

8100
来自专栏机器学习算法工程师

一道网易笔试题引发的血案……

作者:柳行刚 编辑:黄俊嘉 网易的2016年笔试题,题目经典。 所以特地找来给各位有兴趣的童鞋看看, 有详细的解题思路以及代码喔~ 各位,请看题! 题目描述: ...

482120
来自专栏C语言及其他语言

[每日一题]矩阵乘法

本次的题目来源于C语言网比赛栏目八月月赛第一题,记得去试试看看自己能不能AC哦!!! 题目描述 给定一个N阶矩阵A,输出A的M次幂(M是非负整数) 例如: ...

37250

扫码关注云+社区

领取腾讯云代金券