🤵♂️ 个人主页: @计算机魔术师 👨💻 作者简介：CSDN内容合伙人，全栈领域优质创作者。
🌐 推荐一款找工作神器网站: 牛客网 |笔试题库|面试经验|实习招聘内推
还没账户的小伙伴 速速点击链接登录注册吧！🙋♂️
@[toc]
一、说在前面
刷题是一件日积月累的事情，我们在刷题中要保持良好习惯，让每一道题发挥最大作用！以下是 某ACM🥇金牌选手所建议的刷题方式，觉得很不错,给大家参考一下
如何正确的做一道题
- 从简入手: 先从简单暴力(时间复杂度高)的方法入手。
- 优化: 思考如何在第一步的基础上，如何优化算法，降低时间复杂度。
- 构思代码: 有了以上两步，我们此时应该已经有了一个正确的想法，此时我们应该构思代码，有那几部分，每部分实现什么功能，代码怎么写。而不是直接闷头去写代码，没想清楚直接去写代码，会导致写了一半发现思路不对，写的代码都是错误的。
- 写代码: 实现第三步代码。
- (Debug): 如果我们的题目没有通过测试，应该检查代码是不是有bug、思路对不对等。
- 总结与反思: 题目通过了，我们应该总结一下这道题考察的知识点、切入的角度、同类型的题目等，同时思考有没有更优的办法。
要做到以上几点，一道题学得很透彻，遇到同类问题都可以举一反三。
[En]
To achieve the above points, a problem to learn is very thorough, encounter the same type of problems can be cited.
数组&双指针章节
二、两数之和
和 ​hello world​ 一样经典的刷题入门第一题 —— 两数之和
原题如下：
给定一个整 数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并>返回它们的数组下标。
您可以假设每个输入只对应一个答案。但是，数组中的相同元素不能在答案中重复。[En]
You can assume that each input corresponds to only one answer. However, the same element in the array cannot be repeated in the answer.
您可以按任何顺序返回答案。
[En]
You can return the answers in any order.
示例 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 -109 -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)
我们使用哈希表对其进行优化。让我们简单地谈谈哈希表的原理
[En]
We apply hash table to optimize it. Let’s briefly talk about * the principle of hash table *
- 数组的特点是寻址容易，插入和删除困难
[En]
Array is characterized by easy addressing and difficult insertion and deletion*
- 链表的特点是寻址困难，容易插入和删除。
[En]
the linked list is characterized by difficult addressing and easy insertion and deletion.*
我们把两者结合起来，就是哈希表
[En]
We combine the two, which is * 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
执行速度比以前快了十倍，内存消耗也多了一点。
[En]
The execution speed is ten times faster than before, and the memory consumption is a little more.
时间复杂度： ​O(n)​ 空间复杂度: ​O(1)​
这里有一点秒的比较，因为有一个特殊的情况。
[En]
Here is a bit of a comparison of seconds, because there is a special case.
输入：[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];
}
}
速度是以前暴力枚举的十倍，内存消耗保持不变
[En]
Ten times as fast as previous violent enumerations, memory consumption remains unchanged
到这里我们已经成功踏出我们刷题的第一步啦🎉🎉🎉
今日份推荐 —— 牛客网
学习和掌握一门语言的一个快速方法是练习这门语言的语法，并将其与其他语言进行比较，以获得更深的理解和收获！
[En]
A quick way to learn and master a language is to practice the grammar of the language and compare it with other languages to gain a deeper understanding and harvest!
如果还不知道哪里可以适用与 小白 刷题掌握语法，牛客网亲测很不错！！点击链接跳转牛客网登录注册看看，他们现在的IT题库内容很丰富，属于国内做的很好的了，而且是课程+刷题+面经+求职+讨论区分享，一站式求职学习网站，最最最重要的里面的资源全部免费！！
他们的 ​Java & Python​题单是从最基础的输出、字符串格式化输出开始，经过运算符、列表、循环语句、条件语句、元组、字典、函数等知识点，一步一步教你慢慢学会 ​Java & Python​那为数不多的基本语法，最后再配合上8道具有实践意义的综合实践题，可以帮你更加有效的巩固前面学会的知识。
牛客网还提供题解专区和讨论区会有大神提供题解思路，对新手玩家及其友好，有不清楚的语法，不理解的地方，看看别人的思路，别人的代码，也许就能豁然开朗。
如果现在的你按捺不住卷起来，那就赶快点击下方链接学起来吧！ 链接：点击链接跳转牛客网开始刷题之路！！！
如果还没有账号的小伙伴速速点击链接登录注册吧！🙋♂️
Original: https://blog.51cto.com/u_15691039/5637395
Author: 计算机魔术师
Title: 【刷题之路 | Java & Python】两数之和（暴力枚举&哈希表）
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/500216/
转载文章受原作者版权保护。转载请注明原作者出处！