leetcode哈希--经典题目（python）

文章目录

• 前言
• 一、242.有效的字母异位词
• 二、202快乐数
• 三、1两数之和
• 四、454四数相加
• 383赎金信
• 15三数之和
• 18四数之和

---

前言

本文介绍有关哈希的相关题目和算法
哈希表是根据关键码的值而直接进行访问的数据结构。一般哈希表都是用来快速判断一个元素是否出现集合里。
具体概念不必赘述

---

一、242.有效的字母异位词

题目链接
这个题目主要思想是，按着字母表的位置为对应的数组下标，来标记字符串s每个字母出现的次数，再用=减去字符串t出现的次数，如果为0就返回true

二、202快乐数

题目链接

这道题目，主要要学会使用一种哈希数据结构：unordered_set，这个数据结构可以解决很多类似的问题。
题目中说了会 无限循环，那么也就是说求和的过程中，sum会重复出现，那么我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法了。

三、1两数之和

题目链接
本题呢，则要使用map，那么来看一下使用数组和set来做哈希法的局限。

数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。
set是一个集合，里面放的元素只能是一个key，而两数之和这道题目，不仅要判断y是否存在而且还要记录y的下标位置，因为要返回x 和 y的下标。所以set 也不能用。
此时就要选择python种另一种数据结构dict字典： ，diact是一种key value的存储结构，可以用key保存数值，用value在保存数值所在的下标。同时用枚举取当前的值和下标

四、454四数相加

题目链接

本题解题步骤：

1.首先定义 一个dict，key放a和b两数之和，value 放a和b两数之和出现的次数。
2.遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到dict中。
3.定义int变量count，用来统计 a+b+c+d = 0 出现的次数。
4.在遍历大C和大D数组，找到如果 0-(c+d) 在dict中出现过的话，就用count把dict中key对应的value也就是出现次数统计出来。
5.最后返回统计值 count 就可以了

383赎金信

题目链接
需要注意两点。
第一点“为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思” 这里说明杂志里面的字母不可重复使用。
第二点 “你可以假设两个字符串均只含有小写字母。” 说明只有小写字母，这一点很重要，这就可以使用26维数组作为哈希表

15三数之和

题目链接
步骤：
1.先将数组排序
2.在for循环里定义双指针，从头开始遍历，如果i下标大于零直接跳出循环。如果nums[i] + nums[left] + nums[right] > 0 就说明 此时三数之和大了，所以right下标就应该向左移动，这样才能让三数之和小一些。
如果 nums[i] + nums[left] + nums[right] < 0 说明 此时 三数之和小了，left 就向右移动，才能让三数之和大一些，直到left与right相遇为止。
3.在此过程中注意去重

18四数之和

题目链接

四数之和，和三数之和是一个思路，都是使用双指针法, 基本解法就是在三数之和的基础上再套一层for循环。

三数之和 的双指针解法是一层for循环num[i]为确定值，然后循环内有left和right下标作为双指针，找到nums[i] + nums[left] + nums[right] == 0。

四数之和的双指针解法是两层for循环nums[k] + nums[i]为确定值，依然是循环内有left和right下标作为双指针，找出nums[k] + nums[i] + nums[left] + nums[right] == target的情况，三数之和的时间复杂度是 O ( n 2 ) O(n^2) O(n2)，四数之和的时间复杂度是 O ( n 3 ) O(n^3) O(n3) 。