【代码随想录】哈希表-golang
哈希表 from 代码随想录
hash表解法可以是slice,map…，目的是将时间复杂度降为O(1)
有效的字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
排序
思路：直接重新声明字符的字节形式，然后对其进行排序比较
func isAnagram(s, t string) bool {
if len(s) != len(t) {
return false
}
s1 := []byte(s)
s2 := []byte(t)
sort.Slice(s1,func(i,j int) bool{return s1[i] < s1[j]})
sort.Slice(s2,func(i,j int) bool{return s2[i] < s2[j]})
return string(s1) == string(s2)
}
哈希表
时间复杂度O（n） n为s的长度
空间复杂度O（s） s为字符集大小
数组
思路：从另一个角度考虑，t 是 s 的异位词等价于「两个字符串中字符出现的种类和次数均相等」。由于字符串只包含 26 个小写字母，声明两个长度为26的数组，遍历s和t后比较两个数组
func isAnagram(s, t string) bool {
var c1, c2 [26]int
for _, ch := range s {
c1[ch-'a']++
}
for _, ch := range t {
c2[ch-'a']++
}
return c1 == c2
}
map
思路：先初始化一个map，遍历s去存入然后再遍历t去删除
func isAnagram(s, t string) bool {
if len(s) != len(t) {
return false
}
s1 := map[rune]int{}
for _,val := range s {
s1[val]++
}
for _,val := range t {
s1[val]--
if s1[val] < 0 {
return false
}
}
return true
}
两个数组的交集
给定两个数组，编写一个函数来计算它们的交集。
两个集合
如果使用哈希集合存储元素，则可以在 O(1)的时间内判断一个元素是否在集合中，从而降低时间复杂度
时间复杂度和空间复杂度均为O(m+n)，其中 m 和 n 分别是两个数组的长度
func intersection(nums1 []int, nums2 []int)(intersection []int) {
hash1 := map[int]struct{}{}
hash2 := map[int]struct{}{}
for _,val := range nums1{
hash1[val] = struct{}{}
}
for _,val := range nums2{
hash2[val] = struct{}{}
}
if len(hash1) > len(hash2){
hash1,hash2 = hash2,hash1
}
for key,_ := range hash1{
if _,exist := hash2[key];exist{
intersection = append(intersection,key)
}
}
return
}
快乐数
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为：
对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
func isHappy(n int) bool {
m := map[int]bool{}
for ; n!=1 && !m[n];n,m[n] = step(n),true{}
return n == 1
}
c
func step(n int)int{
sum := 0
for n > 0 {
sum += (n%10) * (n%10)
n = n/10
}
return sum
}
两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
思路：可以采取暴力解法，双层for循环结束战斗，但是时间复杂度是O（n2），可以采取hash map用空间换时间来降低时间复杂度
func twoSum(nums []int, target int) []int {
s1 := map[int]int{}
for index,val := range nums{
if prevIndex,ok := s1[target - val];ok{
return []int{prevIndex,index}
}else{
s1[val] = index
}
}
return []int{}
}
四数相加II
将四个数组归为两组 a + b + c + d = 0 --> a + b = -c - d
所以声明一个hashmap将a+b 存入map然后用 -c -d 去命中map
时间复杂度O（n2） 空间复杂度O（n2）
func fourSumCount(nums1 []int, nums2 []int, nums3 []int, nums4 []int)(ans int) {
s1 := map[int]int{}
for _,a := range nums1 {
for _,b := range nums2{
s1[a+b]++
}
}
for _,c := range nums3 {
for _,d := range nums4{
ans += s1[-c-d]
}
}
return
}
赎金信
给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。’
(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)
思路：类似相同字符串那题？
先通过长度过滤，然后将magazine 中的字符存进hashmap中 val++，遍历赎金信去命中hashmap val-- 如果小于0返回false，未命中返回false，最后返回true
时间复杂度O（m+n），空间复杂度O（n）
hashmap 第一次自解
func canConstruct(ransomNote string, magazine string) bool {
if len(ransomNote) > len(magazine) {
return false
}
s1 := map[rune]int{}
for _,val := range magazine{
s1[val]++
}
for _,val := range ransomNote{
if _,ok := s1[val];ok{
s1[val]--
if s1[val] < 0{
return false
}
}else{
return false
}
}
return true
}
数组，leetcode答案 26长度的数组，用 n - 'a’定位
func canConstruct(ransomNote, magazine string) bool {
if len(ransomNote) > len(magazine) {
return false
}
cnt := [26]int{}
for _, ch := range magazine {
cnt[ch-'a']++
}
for _, ch := range ransomNote {
cnt[ch-'a']--
if cnt[ch-'a'] < 0 {
return false
}
}
return true
}
三数之和
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
思路：双指针，固定首个元素然后后两个元素用双指针进行查找，过程中注意检查重复值问题（一旦一个元素重复会造成最后的结果出现重复数组）
func threeSum(nums []int) [][]int {
n := len(nums)
sort.Ints(nums)
ans := make([][]int, 0)
// 枚举 a
for first := 0; first < n; first++ {
// 需要和上一次枚举的数不相同
if first > 0 && nums[first] == nums[first - 1] {
continue
}
// c 对应的指针初始指向数组的最右端
third := n - 1
target := -1 * nums[first]
// 枚举 b
for second := first + 1; second < n; second++ {
// 需要和上一次枚举的数不相同
if second > first + 1 && nums[second] == nums[second - 1] {
continue
}
// 需要保证 b 的指针在 c 的指针的左侧
for second < third && nums[second] + nums[third] > target {
third--
}
// 如果指针重合，随着 b 后续的增加
// 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
if second == third {
break
}
if nums[second] + nums[third] == target {
ans = append(ans, []int{nums[first], nums[second], nums[third]})
}
}
}
return ans
}
四数之和
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。
思路：在三数之和的基础上再加上一层for循环
参考答案思路未剪枝版
func fourSum(nums []int, target int)(ans [][]int) {
n := len(nums)
sort.Ints(nums)
for first := 0;first < n-3 ; first ++ {
if first > 0 && nums[first] == nums[first - 1]{
continue
}
for second := first + 1;second < n-2 ;second ++ {
if second > first + 1 && nums[second] == nums[second - 1]{
continue
}
for left,right := second + 1,n - 1;left < right; {
if sum := nums[first] + nums[second] + nums[left] + nums[right] ;sum == target{
ans = append(ans, []int{nums[first], nums[second], nums[left], nums[right]})
for left ++ ;left < right && nums[left] == nums[left-1];left++{}
for right -- ;left < right && nums[right] == nums[right+1];right--{}
}else if sum < target{
left ++
}else {
right --
}
}
}
}
return ans
}
完整版 - 在 first 和 seocnd的for循环中开始剪枝
func fourSum(nums []int, target int)(ans [][]int) {
n := len(nums)
sort.Ints(nums)
for first := 0;first < n-3 ; first ++ {
//去重 + 剪枝
if first > 0 && nums[first] == nums[first - 1] || nums[first] + nums[n-1] + nums[n-2] + nums[n-3] < target{
continue
}
for second := first + 1;second < n-2 ;second ++ {
//去重 + 剪枝
if second > first + 1 && nums[second] == nums[second - 1] || nums[first] + nums[second] + nums[n-2] + nums[n-1] < target{
continue
}
for left,right := second + 1,n - 1;left < right; {
if sum := nums[first] + nums[second] + nums[left] + nums[right] ;sum == target{
ans = append(ans, []int{nums[first], nums[second], nums[left], nums[right]})
for left ++ ;left < right && nums[left] == nums[left-1];left++{}
for right -- ;left < right && nums[right] == nums[right+1];right--{}
}else if sum < target{
left ++
}else {
right --
}
}
}
}
return ans
}