【代码随想录——哈希表】

1.哈希表理论基础

首先什么是哈希表，哈希表（英文名字为Hash table，国内也有一些算法书籍翻译为散列表，大家看到这两个名称知道都是指hash table就可以了）。
在这里插入图片描述
那么哈希表能解决什么问题呢，一般哈希表都是用来快速判断一个元素是否出现集合里。

哈希法也是牺牲了空间换取了时间，因为我们要使用额外的数组，set或者是map来存放数据，才能实现快速的查找。

2. 有效的字母异位词

在这里插入图片描述

// 判断字符串 t 是否是字符串 s 的字母异位词
func isAnagram(s string, t string) bool {charCount := make(map[rune]int,0)// 若字符串长度不同，直接返回 falseif len(s) != len(t) {return false}// 将字符串转换为字符数组，并对字符数组进行排序sChars := []rune(s)tChars := []rune(t)for i:=0;i<len(sChars);i++{if _,ok:=charCount[sChars[i]];ok{charCount[sChars[i]]++}else{charCount[sChars[i]]=1}}for i:=0;i<len(tChars);i++{char,ok := charCount[tChars[i]]if !ok || char==0{return false}charCount[tChars[i]]--}return true
}

这是官方的一种更简洁的写法：

func isAnagram(s string, t string) bool {if len(s)!=len(t){return false}s_map:=[26]int{}t_map:=[26]int{}for i:=0;i<len(s);i++{s_map[s[i]-'a']++t_map[t[i]-'a']++}return s_map==t_map
}

2.1 字母异位词分组

在这里插入图片描述

2.1.1 第一次的写法，有点慢

func groupAnagrams(strs []string) [][]string {map_style := make([][26]int, 0)str_list := make([][]string, 0)map_index := 0for _, str := range strs {strMap := changeStrToMap(str)index := findCorrectStyle(strMap, map_style, map_index)if index == -1 {//表明这是一个新的stylemap_style = append(map_style, strMap)temp := []string{str}str_list = append(str_list, temp)map_index++} else {str_list[index] = append(str_list[index], str)}}return str_list[0:map_index]
}func changeStrToMap(s string) [26]int {s_map := [26]int{}for i := 0; i < len(s); i++ {s_map[s[i]-'a']++}return s_map
}func findCorrectStyle(strMap [26]int, map_style [][26]int, map_index int) int {for i := 0; i < map_index; i++ {if strMap == map_style[i] {return i}}return -1
}

2.1.2 学习一下高手的写法

确实快，主体思路没什么问题，就是不知道数组也能当做map的key。

func groupAnagrams(strs []string) [][]string {// 没想到数组也可以当做keyhmap := make(map[[26]int][]string)for _, str := range strs {// key 表示str 的字符最多26个，每个字符有多少个key := [26]int{}// 计数for _, ch := range str {// idx 代表字符距离小写字母的距离, b 的话是1idx := ch - 'a'key[idx] ++}hmap[key] = append(hmap[key], str)}result := make([][]string, 0, len(hmap))for _, v := range hmap {result = append(result, v)}   return result
}

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

在这里插入图片描述

func findAnagrams(s string, p string) []int {res := make([]int, 0)if len(s) < len(p) {return res}// 用来存储p中各个小写字母出现的次数pattern := [26]int{}temp := [26]int{}for i := 0; i < len(p); i++ {pattern[p[i]-'a']++temp[s[i]-'a']++}if pattern == temp {res = append(res, 0)}for i := 0; i < len(s)-len(p); i++ {temp[s[i]-'a']--temp[s[i+len(p)]-'a']++if pattern == temp {res = append(res, i+1)}}return res
}

3. 两个数组的交集

在这里插入图片描述

func intersection(nums1 []int, nums2 []int) []int {mp := make(map[int]struct{},0)res := make([]int,0)// 遍历nums1for _,num := range(nums1){mp[num] = struct{}{}}// 遍历nums2for _,num := range(nums2){_,ok := mp[num]if ok{// 查找到相同元素，加入答案。并从mp中删除res = append(res,num)delete(mp,num)}}return res
}

3.1 两个数组的交集②

在这里插入图片描述
和上面的代码只有一点点区别，区别在于这道题目需要记录元素出现的个数。

func intersect(nums1 []int, nums2 []int) []int {mp := make(map[int]int,0)res := make([]int,0)// 遍历nums1for _,num := range(nums1){_,ok := mp[num]if !ok{mp[num]=1}else{mp[num]++}}// 遍历nums2for _,num := range(nums2){_,ok := mp[num]if ok{// 查找到相同元素，加入答案。并从mp中删除res = append(res,num)mp[num]--if mp[num]==0{delete(mp,num)}}}return res
}

4.快乐数

在这里插入图片描述

func isHappy(n int) bool {mp := make(map[int]struct{},0)for n != 1{_,ok := mp[n]if ok {//这个数见过return false}//没见过，就记录一下mp[n] = struct{}{}n = getSum(n)}return true
}func getSum(n int)int{res := 0for n>0{res = res + (n%10)*(n%10)n = n/10}return res
}

5. 两数之和

在这里插入图片描述

func twoSum(nums []int, target int) []int {m:=make(map[int]int)for i,n:= range nums {j,ok:= m[target-n]if ok {return []int{i,j}}m[n]=i}return []int{}
}

6. 四数相加②

在这里插入图片描述
思路：两两组合

func fourSumCount(nums1 []int, nums2 []int, nums3 []int, nums4 []int) int {res := 0mp := make(map[int]int,len(nums1)*len(nums1))//循环遍历nums1和nums2两个数组for i:=0;i<len(nums1);i++{for j:=0;j<len(nums2);j++{num := nums1[i] + nums2[j]if _,ok := mp[num];ok{mp[num]++}else{mp[num]=1}}}//循环遍历nums3和nums4两个数组for i:=0;i<len(nums3);i++{for j:=0;j<len(nums4);j++{num := nums3[i] + nums4[j]if _,ok := mp[-num];ok{res += mp[-num]}}}return res
}

7.赎金信

在这里插入图片描述

func canConstruct(ransomNote string, magazine string) bool {pattern1 := [26]int{}for i:=0;i<len(magazine);i++{pattern1[magazine[i]-'a']++}for i:=0;i<len(ransomNote);i++{pattern1[ransomNote[i]-'a']--if pattern1[ransomNote[i]-'a']<0{return false}}return true
}

8.三数之和

在这里插入图片描述
方法一：哈希表

这题不太适合使用hash来做

方法二：双指针，需要先排序。感觉不够快

func threeSum(nums []int) [][]int {var result [][]intif nums == nil || len(nums) < 3 {return result}slices.Sort(nums)for i := 0; i < len(nums); i++ {if nums[i] > 0 {return result}if i > 0 && nums[i] == nums[i-1] {continue}L := i + 1R := len(nums) - 1for L < R {if nums[i]+nums[L]+nums[R] == 0 {sub := []int{nums[i], nums[L], nums[R]}result = append(result, sub)for L < R && nums[L] == nums[L+1] {L += 1}for L < R && nums[R] == nums[R-1] {R -= 1}L += 1R -= 1}else if nums[i]+nums[L]+nums[R] > 0 {R -= 1} else {L += 1}}}return result
}

9.四数之和

在这里插入图片描述

9.1 利用map的写法

我的方法无法通过测试用例，会超时
在这里插入图片描述

func fourSum(nums []int, target int) [][]int {res := make(map[[4]int]struct{}, 0)mp := make(map[int][]int, 0)for i := 0; i < len(nums); i++ {for j := i + 1; j < len(nums); j++ {temp := nums[i] + nums[j]arr, ok := mp[temp]if !ok {slice := make([]int, 2)slice[0] = islice[1] = jmp[temp] = slice} else {//已有arr = append(arr, i)arr = append(arr, j)mp[temp] = arr}}}for key, arr1 := range mp {toFind := target - keyarr2, ok := mp[toFind]if !ok {continue}for i := 0; i < len(arr1)/2; i++ {for j := 0; j < len(arr2)/2; j++ {index_a, index_b := arr1[i*2], arr1[i*2+1]index_c, index_d := arr2[j*2], arr2[j*2+1]if index_a == index_c || index_a == index_d || index_b == index_c || index_b == index_d {continue}item := []int{nums[index_a], nums[index_b], nums[index_c], nums[index_d]}sort.Ints(item)res[[4]int{item[0], item[1], item[2], item[3]}] = struct{}{}}}}back := [][]int{}for key, _ := range res {back = append(back, key[:])}return back
}

9.2 使用双指针的解法

两层for循环，套用一个左右指针。可以通过剪枝提高算法的运行速度。

func fourSum(nums []int, target int) [][]int {if len(nums) < 4 {return nil}sort.Ints(nums)var res [][]intfor i := 0; i < len(nums)-3; i++ {n1 := nums[i]// if n1 > target { // 不能这样写,因为可能是负数// 	break// }if i > 0 && n1 == nums[i-1] {  // 对nums[i]去重continue}for j := i + 1; j < len(nums)-2; j++ {n2 := nums[j]if j > i+1 && n2 == nums[j-1] {  // 对nums[j]去重continue}l := j + 1r := len(nums) - 1for l < r {n3 := nums[l]n4 := nums[r]sum := n1 + n2 + n3 + n4if sum < target {l++} else if sum > target {r--} else {res = append(res, []int{n1, n2, n3, n4})for l < r && n3 == nums[l+1] { // 去重l++}for l < r && n4 == nums[r-1] { // 去重r--}// 找到答案时,双指针同时靠近r--l++}}}}return res
}