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

计算机魔术师

发布于 2022-11-30 16:22:11

5730

发布于 2022-11-30 16:22:11

文章被收录于专栏：计算机魔术师

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

文章目录

一、说在前面

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

如何正确的做一道题

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

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

数组&双指针章节

二、两数之和

和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

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运行速度快很多，不过使用内存消耗更多一点

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

3.1 哈希表(Hash table)

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

数组的特点是：寻址容易，插入和删除困难；
而链表的特点是：寻址困难，插入和删除容易。

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

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

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

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

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

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

与之前相比执行速度快了十倍, 内存消耗多了一点

时间复杂度： 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];
    }
}