day05休息，day06 有效的字母异位词、两个数组的交集、快乐数、两数之和

题目链接：有效的字母异位词、两个数组的交集、快乐数、两数之和

有效的字母异位词

时间复杂度: O(n)
空间复杂度: O(S), S为字符集大小，这里为26

Go

func isAnagram(s string, t string) bool {// s和t的长度一定是相等的if len(s) != len(t) {return false}// 共有26个字符chars := [26]int{}for _, ch := range s {chars[ch-'a']++}for _, ch := range t {if chars[ch-'a'] == 0 {return false}chars[ch-'a']--}return true
}

两个数组的交集

思路:

1. 遍历nums1, 用map将nums1中的数字进行存储
2. 遍历nums2，查询map中数字是否存在 如果count存在，就将数字加入到结果数组，并将key从map中删除

Go

时间复杂度: O(m+n)
空间复杂度: O(n)

func intersection(nums1 []int, nums2 []int) []int {nums1Map := map[int]struct{}{}result := []int{}// 记录nums1for _, v := range nums1 {if _, ok := nums1Map[v]; !ok {nums1Map[v] = struct{}{}}}// 遍历nums2，寻找交集for _, v := range nums2 {if _, ok := nums1Map[v]; ok {result = append(result, v)delete(nums1Map, v)}}return result
}

快乐数

注意项：计算过程中可能会无限循环，而始终得不到1， 即计算过程中的sum可能会重复，如果sum重复说明遇到了无限循环

go

func isHappy(n int) bool {// 用来收集summ := map[int]bool{}for n != 1 && !m[n] {m[n] = truen = getSum(n)}return n == 1
}func getSum(n int) int {sum := 0for n != 0 {// 获取个位数temp := n % 10sum += temp * temp// 移除掉个位n /= 10}return sum
}

两数之和

思路：value作为map的key，value的index作为map的value
时间复杂度: O(n)
空间复杂度: O(n)

Go

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