欧博app下载:逐日一道 LeetCode (1):两数之和

2021-11-08 164 views 2

扫一扫用手机浏览

弁言

前段时间看到一篇刷 LeetCode 的文章,感想很深,我自己自己上大学的时刻,没怎么研究过算法这一方面,导致自己直到现在算法都不咋地。

一直有心想填补下自己的这个短板,实际上又一直给自己找理由种种推脱。

效果今天晚上吃多了,下定刻意要刷一波 LeetCode 的题,刷题的历程顺便写点文章分享下(其实有很好的督促作用)。

LeetCode 的靠山啥的我就不多先容了,我设计只刷简朴难度和中等难度的题,听说刷了这两个难度基本上就够了,至于难题这个难度,先等我把前两个部门刷完再说。

大致聊一下刷题的套路,先看问题, 5 分钟左右没思绪的直接看谜底,这玩意没思绪是真没设施,没有基础贮备想做题照样有点难题的。

看完谜底自己动手写一下代码,这一点很主要,现在面试许多白板代码,一定要自己写,写会有用加深记忆力。

这个系列的文章设计日更,原本以为不是一件很难的事情,效果当我看到了这个:

1700+ 多道题,纵然刨除掉难题的部门, 2/3 也有 1000+ 道题,我真的是给自己开了一个异常棒的头,这一下把未来两三年的计划都制订好了,我真是哔了狗了。

不外不管怎么样吧,刻意都下好了,那么做照样要做的,对我这个设计感兴趣的同砚可以天天在留言区和我一起打卡,预计每篇文章阅读时长在 3 分钟左右,写代码加调试代码总时长不会跨越半小时。使用的代码为 Java ,若是使用 Python 写的话有点太取巧了。

做事情,主要的是要坚持。

需要代码同伙可以接见我的 GitHub 和 Gitee 获取,天天的代码我会同步提交至这两个代码堆栈:

GitHub:https://github.com/meteor1993/LeetCode

Gitee:https://gitee.com/inwsy/LeetCode

问题:两数之和

给定一个整数数组 nums 和一个目的值 target,请你在该数组中找出和为目的值的那两个整数,并返回他们的数组下标。

你可以假设每种输入只会对应一个谜底。然则,数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

由于 nums[0] + nums[1] = 2 + 7 = 9
以是返回 [0, 1]

思绪

首先整理下思绪,虽然问题的目的是要求一个加法,使用程序直接写加法有点不是那么好写,稍微转变一下,使用目的值 target 减去数组 nums 中的一个值,若是获得的效果也在这个数组中,那么我们就解题完成。

暴力破解

我最先想到的也是最简朴的方案,就是暴力破解,直接两个循环套一下,暴力去算,获得效果:

public int[] twoSum_1(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        int temp = target - nums[i];
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] == temp) {
                return new int[]{i, j};
            }
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

这种方案的瑕玷是时间复杂度有点高,优点是简朴,应该是每个人都能想到的方案。

由于总共有 n 个元素,而对于其中的每个元素来讲,我们都需要遍历整个数组来寻找是否存在它所需要的对应的元素,这将花费 O(n) 的时间。

时间复杂度: \(O(n^2)\)

空间复杂度: O(1) 。

两次哈希表

对暴力破解方案的优化思绪是,整个数组,至少需要迭代一次,关键是在这次迭代中,我们要寻找另一种方案,能比套一层循环更快更高效的找到检查在整个数组中,是否含有我们需要的值。

我们可以借助哈希表来举行寻找,它支持以 「近似」 恒定的时间举行快速查找。

public int[] twoSum_2(int[] nums, int target) {
    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 complement = target - nums[i];
        if (map.containsKey(complement) && map.get(complement) != i) {
            return new int[] {i, map.get(complement)};
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

我们把包罗有 n 个元素的列表遍历两次。由于哈希表将查找时间缩短到 O(1) ,以是时间复杂度为 O(n)。

时间复杂度: O(n) 。

空间复杂度: O(n) 。

一次哈希表:

上面我们是先把数组放到哈希表中,然后再举行遍历,实际上我们可以一边放一边举行遍历操作,直到某一个时刻,打成我们的目的,这时我们可以直接返回数据,剩下没有放到哈希表中的数据也不用再往内里放了。

public int[] twoSum_3(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[] { map.get(complement), i };
        }
        map.put(nums[i], i);
    }
    throw new IllegalArgumentException("No two sum solution");
}

虽然这种方式看着比前面的两次哈希表加倍的高效,实际上时间复杂度和空间复杂度是一致的,同样是:

时间复杂度: O(n) 。

空间复杂度: O(n) 。

,

www.allbetgaming.com

欢迎进入欧博平台网站(www.aLLbetgame.us),www.aLLbetgame.us开放欧博平台网址、欧博注册、欧博APP下载、欧博客户端下载、欧博游戏等业务。

Allbet网站内容转载自互联网,如有侵权,联系www.ALLbetgame.us删除。

本文链接地址:http://www.lijiweihejin.com/post/1438.html

相关文章

发表评论