IT博客汇 | 『代码随想录』哈希表（Hash Map）

『代码随想录』哈希表（Hash Map）

NX の博客发表于 2023-10-30 01:39:58

DAY 6

242.有效的字母异位词

这题没什么好说的

func isAnagram(s string, t string) bool {
    m := map[rune]int{}

    for _, c := range s {
        m[c]++
    }

    for _, c := range t {
        m[c]--
    }

    for _, v := range m {
        if v != 0 {
            return false
        }
    }

    return true
}

349.两个数组的交集

func intersection(nums1 []int, nums2 []int) []int {
    m := map[int]bool{}

    for _, v := range nums1 {
        m[v] = true
    }

    ans := []int{}

    for _, v := range nums2 {
        if m[v] == true {
            ans = append(ans, v)
            m[v] = false
        }
    }

    return ans
}

202.快乐数

func isHappy(n int) bool {
    m := map[int]bool{}

    for n != 1 {
        m[n] = true
        n = calc(n)
        if m[n] == true {
            return false
        }
    }

    return true
}

func calc(n int) int {
    ans := 0

    for n != 0 {
        c := n % 10
        ans += c * c
        n /= 10
    }

    return ans
}

1. 两数之和

经典两数之和

func twoSum(nums []int, target int) []int {
    m := map[int]int{}

    for idx, v := range nums {
        m[target-v] = idx
    }

    for idx, v := range nums {
        if a, ok := m[v]; ok {
            return []int{idx, a}
        }
    }

    return nil
}

DAY 7

454.四数相加 II

很顺理成章的思路

func fourSumCount(nums1 []int, nums2 []int, nums3 []int, nums4 []int) int {
    m := map[int]int{}
    ans := 0

    for _, a := range nums1 {
        for _, b := range nums2 {
            m[a+b]++
        }
    }

    for _, c := range nums3 {
        for _, d := range nums4 {
            ans += m[-(c + d)]
        }
    }

    return ans
}

383.赎金信

func canConstruct(ransomNote string, magazine string) bool {
    m := map[rune]int{}

    for _, c := range magazine {
        m[c]++
    }

    for _, c := range ransomNote {
        m[c]--
    }

    for _, v := range m {
        if v < 0 {
            return false
        }
    }

    return true
}

15.三数之和

再做一遍居然没一次做出来

排序，固定一点，再在后面区间使用双指针

注意去重，有点麻烦

func threeSum(nums []int) [][]int {
    n := len(nums)
    ans := [][]int{}
    sort.Ints(nums)

    for a := 0; a < n-2; a++ {
        if nums[a] > 0 { // 单调性质
            break
        }
        if a > 0 && nums[a] == nums[a-1] { // 去重
            continue
        }

        b, c := a+1, n-1

        for b < c {
            na, nb, nc := nums[a], nums[b], nums[c]
            sum := na + nb + nc

            if sum > 0 {
                c--
            } else if sum < 0 {
                b++
            } else {
                ans = append(ans, []int{na, nb, nc})
                for b < c && nums[b] == nb { // 去重
                    b++
                }
                for b < c && nums[c] == nc { // 去重
                    c--
                }
            }
        }
    }

    return ans
}

18.四数之和

在三数之和上再套一层 for （

~~感觉写的好丑~~

func fourSum(nums []int, target int) [][]int {
    n := len(nums)
    ans := [][]int{}
    sort.Ints(nums)

    for a := 0; a < n-3; a++ {
        if a > 0 && nums[a] == nums[a-1] {
            continue
        }
        for b := a + 1; b < n-2; b++ {
            if b > a+1 && nums[b] == nums[b-1] {
                continue
            }
            c, d := b+1, n-1
            for c < d {
                na, nb, nc, nd := nums[a], nums[b], nums[c], nums[d]
                sum := na + nb + nc + nd

                if sum > target {
                    d--
                } else if sum < target {
                    c++
                } else {
                    ans = append(ans, []int{na, nb, nc, nd})
                    for c < d && nc == nums[c] {
                        c++
                    }
                    for c < d && nd == nums[d] {
                        d--
                    }
                }
            }
        }
    }
    return ans
}