哈希表 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)
}

哈希表

时间复杂度On n为s的长度
空间复杂度Os 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循环结束战斗但是时间复杂度是On2可以采取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
时间复杂度On2 空间复杂度On2

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

时间复杂度Om+n空间复杂度On

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
}