T1 - T10

1. 两数之和

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

func twoSum(nums []int, target int) []int {
    intMap := make(map[int]int)
    for i, num := range nums {
        complement := target - num
        if idx, ok := intMap[complement]; ok {
            return []int{idx, i}
        }
        intMap[num] = i
    }
    return nil
}

本题考察 Go 里的 make 函数使用和如何创建 map。

Go 里使用 make 来创建并初始化三种内置的引用数据：切片、映射和通道，他返回的是类型本身而不是指针，因为这些类型在使用前必须初始化其内部数据结构，否则无法直接操作，比如：向 nil map 赋值会出现 panic。

初始化一个 map 有两种方式：

1
2
3
4
5
6
7

// 使用make函数（最常用）
m := make(map[int]int)
// 创建map字面量
m := map[int]int{
    1: 100,
    2: 200
} // 空map: m := map[int]int{}

map 的基本用法如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

// 创建并初始化
m := make(map[int]string)
// 添加键值对
m[1] = "apple"
m[2] = "banana"
// 提取值和处理异常
if v, ok := m[1]; ok {
    // v exist, ok == true
    // v not exist, ok == false
    fmt.Println("v exist! value is: ", v)
} else {
    fmt.Println("v not exist!")
}
// 删除键值对
delete(m, 1)
// 获取长度
fmt.Println(len(m))

2. 字母异位词分组

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func groupAnagrams(strs []string) [][]string {
    // 创建并初始化映射 key: string, value: []string
    m := make(map[string][]string)
    // 字符串自身排序
    for _, str := range strs {
        tmp := []byte(str)
        slices.Sort(tmp)
        sortedS := string(tmp)
        // 向映射中添加排序后的字符串
        m[sortedS] = append(m[sortedS], str)
    }
    return slices.Collect(maps.Values(m))
}

考察 string 类型的自身排序，以及 Collect 函数和 byte 类型。在 Go 语言中，byte是一个非常基础且重要的类型。理解它的核心在于记住一句话：byte 是 uint8 的别名。

1

type byte = uint8

为什么要用 byte ？

虽然 byte 本质是数字，但在语义上，Go 使用 byte 来强调这个数据是原始二进制数据或 ASCII 字符，而不是一个普通的计数数字。在处理字符串时，Go 的字符串底层就是由 []byte 组成的。处理 IO 时，无论是读取文件、网络传输还是编码，比如 JSON 和 Base64，基本都是以 []byte来作为数据载体。

一个字符串变量，经过 []byte 转换后变成了什么呢？

1
2
3
4
5
6
7
8

func main() {
	var s string
	s = "hello world"
	tmp := []byte(s)
	fmt.Printf("%T\n", tmp)
	fmt.Printf("%v\n", tmp)
	fmt.Printf("%d\n", len(tmp))
}

alt text

3. 最长连续序列

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

func longestConsecutive(nums []int) int {
    numSet := make(map[int]bool)
    for _, num := range nums {
        numSet[num] = true
    }
    for num := range numSet {
        numSet[num] = true
    }
    maxLen := 0
    for num := range numSet {
        if !numSet[num - 1] {
            tmpNum := num
            curLen := 1
            for numSet[tmpNum + 1] {
                tmpNum++
                curLen++
            }
            if (curLen > maxLen) {
                maxLen = curLen
            }
        }
    }
    return maxLen
}

这是一开始通过的代码，但是时间开销很大，于是我寻找方法优化。后来知道，map 的遍历速度比 slice 慢。

CPU 并不是一个字节一个字节读内存的，而是按 Cache Line读取，通常是 64 字节。当我访问 slice[0] 时，slice[1] 到 slice[7] 往往已经被悄悄加载进缓存了，访问速度是纳秒级。Map 的底层是数组 + 链表。即便桶是连续的，但里面的 Key/Value 可能会指向其他内存地址，且哈希分布是随机的。CPU 无法预测你下一步要读哪里，只能频繁去主存 RAM 里找，速度慢了一个数量级。

但是在本题中不用担心这个问题导致的结果差异，因为 nums 里的元素没有去重，反而会导致访问速度变慢，而 numSet 里的元素都是唯一的，所以更快。

那么，到底如何优化呢？切入点如下：

1

numSet := make(map[int]struct{}, len(nums))

这里，我们对 numSet 进行了容量的初始化，使得程序在运行过程中无需对它进行一遍又一遍的扩容，减少了扩容带来的时间开销。不仅如此，通过巧妙利用空结构体 struct{} 可以实现零内存占用，如果使用 bool，每个键值对的值部分还要额外占用 1 字节的空间。虽然看起来小，但如果处理百万数据，内存差距和缓存命中率就会显现出来了。

于是，优化后的结果是：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

func longestConsecutive(nums []int) int {
    numSet := make(map[int]struct{}, len(nums))
    for _, num := range nums {
        numSet[num] = struct{}{}
    }
    maxLen := 0
    for num := range numSet {
        if _, ok := numSet[num - 1]; !ok {
            tmpNum := num
            curLen := 1
            for {
                if _, hasNext := numSet[tmpNum + 1]; hasNext {
                    curLen++
                    tmpNum++
                } else {
                    break
                }
            }
            if (curLen > maxLen) {
                maxLen = curLen
            }
        }
    }
    return maxLen
}

运行速度从 8% 提升至 90% !

4. 移动零

采用快慢指针来做，快指针 fast 用来遍历数组，而慢指针 slow 用来指向非零元素，当遍历到 0 时，交换快慢指针指向的元素即可。同时，使用 while 循环来实现。

但是，go 语言坚持“少即是多”的哲学，所以在 go 语言里，while 循环和 for 循环都用 for 语句来实现。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

// while 循环
count := 0
for count < 5 {
    fmt.Println("count is: ", count)
    count++
}
// do-while 循环
for {
    fmt.Println("loop process")
    if !condition {
        // condition: 循环终止条件
        break
    }
}
// 实现无限 for 循环
for {
    if emergency {
        break
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func moveZeroes(nums []int)  {
    fast := 0
    slow := 0
    length := len(nums)

    for fast < length {
        if nums[fast] != 0 {
            if fast != slow {
                nums[fast], nums[slow] = nums[slow], nums[fast]
            }
            slow++
        }
        fast++
    }
}

5. 盛最多水的容器

alt text

这道题目，先尝试用双层循环暴力求解。

（1）暴力循环

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

func maxArea(height []int) int {
    ans := 0
    length := len(height)
    for right := 1; right < length; right++ {
        for left := 0; left < right; left++ {
            width := right - left
            ans = max(ans, width * min(height[left], height[right]))
        }
    }
    return ans 
}

理所当然的，TLE 了。

alt text

所以我们改用另一种方法——对撞指针。

（2）对撞指针

我们用 left, right 分别表示左右端的两个柱子。

关键决策： 接下来该移动哪根柱子？

如果移动长柱子：宽度变小，高度要么不变（受短柱子限制），要么变小。面积一定会变小。如果移动短柱子：宽度变小，但如果换到一根更长的柱子，高度可能会增加，从而补偿宽度的损失，使总面积变大。

因此，策略就是：谁短移动谁。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

func maxArea(height []int) int {
    ans := 0
    left := 0
    right := len(height) - 1
    for left != right {
        ans = max(ans, (right - left) * min(height[right], height[left]))
        if height[left] >= height[right] {
            right--
        } else {
            left++
        }
    }
    return ans 
}

6. 三数之和

判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。

其实可以转换为“两数之和”的问题，也就是是否存在两个不同元素满足 nums[i] + nums[j] = -nums[k]。

当然，不可以无序地遍历数组，那样太麻烦了。我们可以先给数组排序，再进行遍历和寻找满足条件的三元组。

由于 nums[i] + nums[j] + nums[k] == 0，所以：

sum < 0: 需要更大的，向右

sum > 0: 需要更小的，向左

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

func threeSum(nums []int) [][]int {
    sort.Ints(nums)
    res := [][]int{}
    n := len(nums)
    for i := 0; i < n - 2; i++ {
        if nums[i] > 0 {
            break;
        }

        // 去重
        if i > 0 && nums[i] == nums[i - 1] {
            continue
        }
        l := i + 1
        r := n - 1
        for l < r {
            sum := nums[i] + nums[l] + nums[r]
            if sum == 0 {
                res = append(res, []int{nums[i], nums[l], nums[r]})

                for l < r && nums[l] == nums[l + 1] { l++ }
                for l < r && nums[r] == nums[r - 1] { r-- }
                l++
                r--
            } else if sum < 0 {
                l++
            } else {
                r--
            }
        }
    }
    return res
}

7. 接雨水

这道题是上面 T5 的进阶。

这里介绍两种方法。

（1）暴力法

a 先找到最高的柱子为 mid

b 然后分别从左往右和从右往左来寻找可以接雨水的低洼地带

c 定义左侧或右侧临时最高的柱子为 preH，所以接雨水的计算公式为：ans += (preH - height[left]) 或 ans += (preH - height[right])

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

func trap(height []int) int {
    maxH := 0
    mid := 0
    for idx, i := range height {
        if i > maxH {
            maxH = i
            mid = idx    
        }
    }
    ans := 0
    
    preH := height[0]
    for left := 1; left < mid; left++ {
        if height[left] >= preH {
            preH = height[left]
        } else if height[left] < preH {
            ans += (preH - height[left])
        }
    }
    preH = height[len(height) - 1]
    for right := len(height) - 1; right > mid; right-- {
        if height[right] >= preH {
            preH = height[right] 
        } else if height[right] < preH {
            ans += (preH - height[right])
        }
    }

    return ans
}

（2）动态规划

动态规划的做法和上述的暴力很像，只不过是先求出两个数组：leftMax[] 和 rightMax[] 来存放第 i 个柱子左侧和右侧的最高柱子的高度。这样就可以只做一次遍历，并在 O(1) 的时间复杂度内获取接到的雨水量。

注意：不能接到雨水，看左右两边的较高柱子中较矮的那一个。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

func trap(height []int) int {
    ans, n := 0, len(height)
    if n == 0 { return ans }
    leftMax := make([]int, n)
    rightMax := make([]int, n)
    leftMax[0], rightMax[n - 1] = height[0], height[n - 1]
    for left := 1; left < n; left++ {
        leftMax[left] = max(leftMax[left - 1], height[left])
    }
    for right := n - 2; right >= 0; right-- {
        rightMax[right] = max(rightMax[right + 1], height[right])
    }
    // 能不能接到雨水，看左右两边的较高柱子中较矮的那一个
    for idx, val := range height {
        subH := min(leftMax[idx], rightMax[idx])
        ans += (subH - val)
    }
    return ans
}

8. 无重复字符的最长子串

本题考察的是对滑动窗口的理解。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func lengthOfLongestSubstring(s string) int {
    n := len(s)
    m := make(map[byte]bool, n)
    left := 0
    maxLen := 0
    for right := 0; right < n; right++ {
        for m[s[right]] {
            delete(m, s[left])
            left++
        }
        m[s[right]] = true
        if right - left + 1 > maxLen {
            maxLen = right - left + 1
        }
    }
    return maxLen 
}

9. 找到字符串中所有字母异位词

本题其实是上一题的变体，是指在滑动窗口时还要判断是否符合异位词的条件。

a 窗口大小固定，必须等于字符串 p 的长度 b 查看频率表中的字符出现次数是否和 p 一致

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

func findAnagrams(s string, p string) []int {
    sLen, pLen := len(s), len(p)
    // 边界条件
    if sLen < pLen {
        return []int{}
    }
    var res []int
    // 创建频率表
    pCount, sCount := [26]int
    // 创建第一个窗口并开始记录字符出现的频率
    for i := 0; i < pLen; i++ {
        pCount[p[i] - 'a']++
        sCount[s[i] - 'a']++
    }
    // 判断第一个窗口
    if sCount == pCount {
        res = append(res, 0)
    }
    for i := 0; i < sLen - pLen; i++ {
        sCount[s[i] - 'a']--
        pCount[s[i + pLen] - 'a']++
        if sCount == pCount {
            res = append(res, i + 1)
        }
    }
    return res
}

10. 和为 K 的子数组

这题要用前缀和+哈希表来做，代码很短。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func subarraySum(nums []int, k int) int {
    count := 0
    curSum := 0
    m := make(map[int]int)
    m[0] = 1
    for _, num := range nums {
        curSum += num
        // sum[i, j] = pre[i] - pre[j - 1] -> sum == k
        if val, ok := m[curSum - k]; ok {
            count += val
        }
        m[curSum]++
    }
    return count
}