【Leetcode之路 | Java & Python】两数之和(暴力枚举&哈希表)

【Leetcode之路 | Java & Python】两数之和(暴力枚举&哈希表)

🤵‍♂️ 个人主页: @计算机魔术师
👨‍💻 作者简介:CSDN内容合伙人,全栈领域优质创作者。

一、说在前面

刷题是一件日积月累的事情,我们在刷题中要保持良好习惯,让每一道题发挥最大作用!以下是 某ACM🥇金牌选手所建议的刷题方式,觉得很不错,给大家参考一下

如何正确的做一道题

  1. 从简入手: 先从简单暴力(时间复杂度高)的方法入手。
  2. 优化: 思考如何在第一步的基础上,如何优化算法,降低时间复杂度。
  3. 构思代码: 有了以上两步,我们此时应该已经有了一个正确的想法,此时我们应该构思代码,有那几部分,每部分实现什么功能,代码怎么写。而不是直接闷头去写代码,没想清楚直接去写代码,会导致写了一半发现思路不对,写的代码都是错误的。
  4. 写代码: 实现第三步代码。
  5. (Debug): 如果我们的题目没有通过测试,应该检查代码是不是有bug、思路对不对等。
  6. 总结与反思: 题目通过了,我们应该总结一下这道题考察的知识点、切入的角度、同类型的题目等,同时思考有没有更优的办法。

做到以上几点,一道题学习的就很透了,遇到同类型的题目可以举一反三啦。

数组&双指针章节

二、两数之和

hello world 一样经典的刷题入门第一题 —— 两数之和

原题如下:

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

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1:

输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。

示例 2:

输入:nums = [3,2,4], target = 6
输出:[1,2]

示例 3:

输入:nums = [3,3], target = 6
输出:[0,1]

提示:

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案

进阶:你可以想出一个时间复杂度小于 O(n2) 的算法吗?

思路历程:

2.1、暴力枚举

按照解题思路,暴力枚举,这里选择快速排序法,快速筛选

2.1.1 python实现

代码:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        result = []
        for i in range(len(nums)):
            for j in range(i+1,len(nums)):
                if target == nums[i] + nums[j]:
                    result.append(i)
                    result.append(j)

        return result

【Leetcode之路 | Java & Python】两数之和(暴力枚举&哈希表)

2.1.2 java实现

代码:

class Solution {
    public int[] twoSum(int[] nums, int target) {
        List<Integer> result = new ArrayList<Integer>();
        for(int i=0;i<nums.length;i++){
            for(int j=i+1;j<nums.length;j++){
                if(target == nums[i]+nums[j])
                    return new int[]{i,j};
            }
        }
        return null;
    }
}

可以看出java作为编译性语言还是要比python运行速度快很多,不过使用内存消耗更多一点
【Leetcode之路 | Java & Python】两数之和(暴力枚举&哈希表)

时间复杂度为 O(n2)
空间复杂度O(1)

3.1 哈希表(Hash table)

我们适用哈希表对其优化,我们先简单讲讲哈希表的原理

我们把两者结合起来,便是哈希表

哈希表的底层实际上是基于数组来存储的,当插入键值对时,并不是直接插入该数组中,而是通过对键进行Hash运算得到Hash值,然后和数组容量取模,得到在数组中的位置后再插入(不害怕多个重复数字,使用链表把多个数字都压缩在同一个值上)。取值时,先对指定的键求Hash值,再和容量取模得到底层数组中对应的位置,如果指定的键值与存贮的键相匹配,则返回该键值对,如果不匹配,则表示哈希表中没有对应的键值对。这样做的好处是在查找、插入、删除等操作可以做到O(1),最坏的情况是O( n ),当然这种是最极端的情况,极少遇到。

【Leetcode之路 | Java & Python】两数之和(暴力枚举&哈希表)

哈希表实现原理很多,不管哪门语言,实现一个HashMap的过程均可分为三大步骤:

  1. 实现一个Hash函数
  2. 合理解决Hash冲突
  3. 实现HashMap的操作方法

我们这里不深揪算法,大概了解即可,pythondict便是哈希表算法,我们直接使用即可。

3.1.1 python实现

代码:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        result = []
        Hashmap = dict()
        for i,num in enumerate(nums):
            if target - num  in Hashmap:
                result.append(Hashmap[target - num])
                result.append(i)
            Hashmap[nums[i]] = i # 默认会把本次数值省略

        return result

【Leetcode之路 | Java & Python】两数之和(暴力枚举&哈希表)
与之前相比执行速度快了十倍, 内存消耗多了一点

时间复杂度O(n)
空间复杂度: O(1)

这里提一点比较秒的地方,因为有一种情况是比较特殊的

输入:
[3,2,4]
6

这个时候如果正常遍历所有数,会有可能添加到3,因为 6 – 3 = 3 在nums里面,即自己和自己相加了。解决办法: 错开索引,在当前索引在字典创建对应值,跳过本次循环到下一个值判断。

3.1.2 Java实现

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer>  hashmap = new HashMap<Integer,Integer>();
        List<Integer>  result = new ArrayList<Integer>();
        for(int i=0;i < nums.length;i++){
            if (hashmap.containsKey(target - nums[i])){
                return new int[]{hashmap.get(target - nums[i]),i};
            }
            hashmap.put(nums[i],i);
        }
        return new int[0];
    }
}

【Leetcode之路 | Java & Python】两数之和(暴力枚举&哈希表)
与之前暴力枚举同样快速十倍,内存消耗没有变化

到这里我们已经成功踏出我们刷题的第一步啦🎉🎉🎉

共计人评分,平均

到目前为止还没有投票!成为第一位评论此文章。

(0)
心中带点小风骚的头像心中带点小风骚普通用户
上一篇 2023年3月10日 上午8:42
下一篇 2023年3月10日 上午8:43

相关推荐