每日一道 LeetCode (1):两数之和

每日一道 LeetCode (1):两数之和插图

引言

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

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

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

LeetCode 的背景啥的我就不多介绍了,我计划只刷简单难度和中等难度的题,据说刷了这两个难度基本上就够了,至于困难这个难度,先等我把前两个部分刷完再说。

大致聊一下刷题的套路,先看题目, 5 分钟左右没思路的直接看答案,这玩意没思路是真没办法,没有基础储备想做题还是有点困难的。

看完答案自己动手写一下代码,这一点很重要,现在面试很多白板代码,一定要自己写,写会有效加深记忆力。

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

每日一道 LeetCode (1):两数之和插图(1)

1700+ 多道题,即使刨除掉困难的部分, 2/3 也有 1000+ 道题,我真的是给自己开了一个非常棒的头,这一下把未来两三年的规划都制定好了,我真是哔了狗了。

每日一道 LeetCode (1):两数之和插图(2)

不过不管怎么样吧,决心都下好了,那么做还是要做的,对我这个计划感兴趣的同学可以每天在留言区和我一起打卡,预计每篇文章阅读时长在 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) 。

本站资源均源自网络,若涉及您的版权、知识产权或其他利益,请附上版权证明邮件告知。收到您的邮件后,我们将在72小时内删除。
若下载资源地址错误或链接跳转错误请联系站长。站长q:770044133。

» 每日一道 LeetCode (1):两数之和

发表评论

免登录下载网,提供全网最优质的资源集合!