「算」 04. 哈希表

哈希表相关题目。

1 概念

哈希表（Hash table）用来快速判断一个元素是否出现集合里。

1.1 哈希函数

比如把学生的姓名直接映射为哈希表上的索引，然后就可以通过查询索引下标快速知道这位同学是否在这所学校里了。哈希函数通过 hashCode 把名字转化为数值，一般 hashCode 是通过特定编码方式，可以将其他数据格式转化为不同的数值，这样就把学生名字映射为哈希表上的索引数字了。

1.2 哈希碰撞

如图所示，小李和小王都映射到了索引下标 1 的位置，这一现象叫做哈希碰撞。

• 拉链法

  刚刚小李和小王在索引 1 的位置发生了冲突，发生冲突的元素都被存储在链表中，这样我们就可以通过索引找到小李和小王了。

  

  数据规模是 dataSize， 哈希表的大小为 tableSize。

• 线性探测法

  使用线性探测法，一定要保证 tableSize 大于 dataSize。我们需要依靠哈希表中的空位来解决碰撞问题。例如冲突的位置放了小李，那么就向下找一个空位放置小王的信息。

2 题目

2.1 字母异位词

给定两个字符串 s 和 t，编写一个函数来判断 t 是否是 s 的字母异位词。

func isAnagram1(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
}

func isAnagram2(s, t string) bool {
    if len(s) != len(t) {
        return false
    }
    cnt := map[rune]int{}
    for _, ch := range s {
        cnt[ch]++
    }
    for _, ch := range t {
        cnt[ch]--
        if cnt[ch] < 0 {
            return false
        }
    }
    return true
}

2.2 快乐数

编写一个算法来判断一个数 n 是不是快乐数。

func isHappy(n int) bool {
    resMap := make(map[int]bool)
    for resMap[n] == false {
        if sqSum(n) == 1 {
            return true
        }
        resMap[n] = true
        n = sqSum(n)
    }
    return false
}

func sqSum(n int) int {
    var sum int
    for n > 0 {
        sum += (n%10) * (n%10)
        n /= 10
    }
    return sum
}

2.3 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。

func twoSum(nums []int, target int) []int {
    m := make(map[int]int)
    for index, val := range nums {
        if preIndex, ok := m[target-val]; ok {
            return []int{preIndex, index}
        } else {
            m[val] = index
        }
    }
    return []int{}
}

2.4 三数之和

给你一个整数数组 nums，判断是否存在三元组满足 nums[i] + nums[j] + nums[k] == 0。请你返回所有和为 0 且不重复的三元组。

func threeSum(nums []int) [][]int {
    res := [][]int{}
    sort.Ints(nums)
    for i := 0; i < len(nums)-2; i++ {
        left, right := i+1, len(nums)-1 
        target := -nums[i]
        if target < 0 {
            break
        }
        if i > 0 && nums[i] == nums[i-1] {
			continue
		}
        for left < right {
            if nums[left] + nums[right] > target {
                right--
            } else if nums[left] + nums[right] < target {
                left++
            } else {
                res = append(res, []int{nums[i], nums[left], nums[right]})
                left++
                right--
                // Skip duplicates
                for left < right && nums[left] == nums[left-1] {
                    left++
                }
                for left < right && nums[right] == nums[right+1] {
                    right--
                }
            }
        }
    }
    return res
}

此题使用哈希表去重非常困难，建议使用双指针。

2.5 四数之和