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

作者：计算机魔术师

2022 年 8 月 31 日
广东
本文字数：2920 字
阅读完需：约 10 分钟

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

🌐 推荐一款找工作神器网站: 牛客网 |笔试题库|面试经验|实习招聘内推

还没账户的小伙伴 速速点击链接登录注册吧！🙋‍♂️ 刷题通关之路等你冲！！🎉🎉🎉 开始刷爆题库，速速通关面试吧🙋‍♂️\

@[toc]

一、说在前面

刷题是一件日积月累的事情，我们在刷题中要保持良好习惯，让每一道题发挥最大作用！以下是某 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];    }}

复制代码

与之前暴力枚举同样快速十倍，内存消耗没有变化

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

今日份推荐 —— 牛客网

学习掌握一门语言的快速方法就是通过刷题实践运用该语言的语法以及与其他语言的比较也可以得到更深的领悟和收获！

如果还不知道哪里可以适用与小白刷题掌握语法，牛客网亲测很不错！！点击链接跳转牛客网登录注册看看，他们现在的 IT 题库内容很丰富，属于国内做的很好的了，而且是课程+刷题+面经+求职+讨论区分享，一站式求职学习网站，最最最重要的里面的资源全部免费！！

他们的Java & Python题单是从最基础的输出、字符串格式化输出开始，经过运算符、列表、循环语句、条件语句、元组、字典、函数等知识点，一步一步教你慢慢学会Java & Python那为数不多的基本语法，最后再配合上 8 道具有实践意义的综合实践题，可以帮你更加有效的巩固前面学会的知识。