数据结构与算法：哈希表（附有leetcode题242、349、1、454、438、15、18题解）

本文主要是介绍数据结构与算法：哈希表（附有leetcode题242、349、1、454、438、15、18题解），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

哈希表的数据结构

哈希表用到的数据结构一共有三种：数组、set、map
一般情况下，如果元素较少且连续，那么用数组。
如果元素很多，那么用set。
如果元素很离散，或者存在kv结构，那么用map（python中是dict）

哈希表使用场景

判断某一个元素是否在某集合中出现过，出现了几次

纯哈希表

leetcode242.有效的字母异位词（数组结构）

知识点：注意python中用ord()来获取ASCII码

class Solution(object):def isAnagram(self, s, t):""":type s: str:type t: str:rtype: bool"""arr = [0] * 26s_size = len(s)t_size = len(t)if s_size != t_size:return Falsefor i in range(s_size):arr[ord(s[i]) - ord('a')] += 1arr[ord(t[i]) - ord('a')] -= 1for i in range(26):if arr[i] != 0:return Falsereturn True

leetcode349.两个数组的交集（数组结构/set结构）

纯数组结构

知识点：list列表添加元素用append

class Solution(object):def intersection(self, nums1, nums2):""":type nums1: List[int]:type nums2: List[int]:rtype: List[int]"""arr = [0]*1001ans = list()n = len(nums1)m = len(nums2)for i in range(n):if arr[nums1[i]] == 0:arr[nums1[i]] = 1for i in range(m):if arr[nums2[i]] == 1:ans.append(nums2[i])arr[nums2[i]] = 0return ans

set结构

知识点：求交集操作用&

class Solution(object):def intersection(self, nums1, nums2):""":type nums1: List[int]:type nums2: List[int]:rtype: List[int]"""arr1 = set(nums1)arr2 = set(nums2)return list(arr1 & arr2)

leetcode1.两数之和（map结构）

http://t.csdnimg.cn/HJm6C
知识点：enumerate的使用同时返回数据和数据下标

class Solution(object):def twoSum(self, nums, target):""":type nums: List[int]:type target: int:rtype: List[int]"""n = len(nums)arr = dict()for i in range(n):# 查看对应的差值有没有在集合出现过index = target - nums[i]if index in arr:return [i, arr[index]]# 存放遍历过的元素arr[nums[i]] = i

leetcode454.四数相加Ⅱ（map结构）

知识点：用.get()来防止KeyError错误

class Solution(object):def fourSumCount(self, nums1, nums2, nums3, nums4):""":type nums1: List[int]:type nums2: List[int]:type nums3: List[int]:type nums4: List[int]:rtype: int"""# 将nums1和nums2分为一组，将nums3和nums4分为一组，就重新回到了两数之和的模式。但组内遍历必须是o(n^2)了size1 = len(nums1)size2 = len(nums2)size3 = len(nums3)size4 = len(nums4)tmp = dict()ans = 0for i in range(size1):for j in range(size2):index = nums1[i] + nums2[j]if index in tmp:tmp[index] += 1else:tmp[index] = 1# tmp[index] = tmp.get(index, 0) + 1# 防止键不存在报错for i in range(size3):for j in range(size4):index = 0 - nums3[i] - nums4[j]if index in tmp:ans += tmp[index]# ans += tmp.get(index, 0)return ans

哈希表+滑动窗口

leetcode438.找到字符串中所有字母异位词

http://t.csdnimg.cn/AMj0X

容易想用哈希表做的题目

leetcode15.三数之和

**为什么不能用哈希表做：**因为这道题要求去重，那么对于三个元素都需要去重，哈希表本身去重的话只能依赖于set结构的去重特性，但是这样就需要开三个set了，非常麻烦，所以需要用双指针。
知识点：如果set里面的元素是不能hash的元素，需要先将元素转为不可变的tuple元组（元组是可以hash的），才能继续使用set的去重特性。

class Solution(object):def threeSum(self, nums):""":type nums: List[int]:rtype: List[List[int]]"""ans = set()n = len(nums)nums = sorted(nums)for i in range(n-2):left = i+1right = n-1while left!=right:tmp = nums[i]+nums[left]+nums[right]if tmp > 0:right -= 1elif tmp < 0:left += 1else:triplet = (nums[i], nums[left], nums[right])ans.add(triplet)left += 1return list(ans)

leetcode18.四数之和

class Solution(object):def fourSum(self, nums, target):""":type nums: List[int]:type target: int:rtype: List[List[int]]"""ans = set()n = len(nums)nums = sorted(nums)for i in range(n-3):for j in range(i+1, n-2):left = j+1right = n-1while left != right:tmp = nums[i]+nums[j]+nums[left]+nums[right]if tmp < target:left += 1elif tmp > target:right -= 1else:triplet = (nums[i], nums[j], nums[left], nums[right])ans.add(triplet)left += 1return list(ans)

这篇关于数据结构与算法：哈希表（附有leetcode题242、349、1、454、438、15、18题解）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---