第二周 哈希表、集合、映射、前缀和、差分、双指针扫描

题目数：16

本周作业

• 811.子域名访问计数

（Easy）半年内出题频次：

func subdomainVisits(cpdomains []string) (ans []string) {
    h := map[string]int{}
    for _, cpdomain := range cpdomains {
        cp := strings.Split(cpdomain, " ")
        count, _ := strconv.Atoi(cp[0])
        domains := strings.Split(cp[1], ".")
        cur := ""
        for i := len(domains) - 1; i >= 0; i-- {
            if cpdomain == "" {
                cur = domains[i]
            } else {
                cur = domains[i] + "." + cur
            }
            h[cur] += count
        }
    }
    for domain, cnt := range h {
        ans = append(ans, fmt.Sprintf("%d %s", cnt, domain))
    }
    return ans
}

• 697.数组的度

（Easy）半年内出题频次：

func findShortestSubArray(nums []int) (ans int) {
    type stat struct {cnt, l, r int}
    ht := map[int]stat{}
    for i, num := range nums {
        if st, ok := ht[num]; ok {
            st.cnt++
            st.r = i
            ht[num] = st
        } else {
            ht[num] = stat{1, i, i}
        }
    }
    maxCnt := 0
    for _, st := range ht {
        if st.cnt > maxCnt {
            maxCnt, ans = st.cnt, st.r - st.l + 1
        } else if st.cnt == maxCnt {
            if st.r - st.l + 1 < ans {
                ans = st.r - st.l + 1 
            }
        }
    }
    return ans
}

• 560.和为 K 的子数组

（Medium）半年内出题频次：

// 方法一：模拟
func subarraySum(nums []int, k int) int {
    cnt := 0
    for start := 0; start < len(nums); start++ {
        sum := 0
        for end := start; end >= 0; end-- {
            sum += nums[end]
            if sum == k {
                cnt++
            }
        }
    }
    return cnt
}

// 方法二：前缀和
func subarraySum(nums []int, k int) int {
    n, cnt := len(nums), 0
    preSum := make([]int, n + 1)
    for i := 1; i <= n; i++ {
        preSum[i] = preSum[i-1] + nums[i-1]
    }
    for left := 1; left <= n; left++ {
        for right := left; right <= n; right++ {
            if preSum[right] - preSum[left-1] == k {
                cnt++
            }   
        }
    }
    return cnt
}

// 方法三：前缀和 + 哈希表
func subarraySum(nums []int, k int) (cnt int) {
    pre := 0
    m := map[int]int{}
    m[0] = 1
    for _, num := range nums {
        pre += num
        if c, ok := m[pre-k]; ok {
            cnt += c
        }
        m[pre]++
    }
	return cnt
}

• 1074.元素和为目标值的子矩阵数量

（Hard）半年内出题频次：

// 写法一：
func numSubmatrixSumTarget(matrix [][]int, target int) (ans int) {
    for i := range matrix { // 枚举上边界
        sum := make([]int, len(matrix[i]))
        for _, row := range matrix[i:] { // 枚举下边界
            for c, v := range row {
                sum[c] += v // 更新每列的元素和
            }
            ans += subarraySum(sum, target)
        }
    }
    return ans
}

func subarraySum(nums []int, k int) (ans int) {
    h := map[int]int{0: 1}
    for pre, i, n := 0, 0, len(nums); i < n; i++ {
        pre += nums[i]
        if cnt, ok := h[pre - k]; ok {
            ans += cnt
        }
        h[pre]++
    }
    return ans
}


// 写法二：
func numSubmatrixSumTarget(matrix [][]int, target int) int {
    m, n, ans := len(matrix), len(matrix[0]), 0
    for i := 0; i < m; i++ {
        sum := make([]int, n)
        for j := i; j < m; j++ {
            for c := 0; c < n; c++ {
                sum[c] += matrix[j][c]
            }
            ans += subarraySum(sum, target)
        }
    }
    return ans
}

func subarraySum(sum []int, k int) (ans int) {
    h := map[int]int{0: 1}
    pre := 0
    for _, num := range sum {
        pre += num
        if cnt, ok := h[pre - k]; ok {
            ans += cnt
        }
        h[pre]++
    }
    return ans
}

实战例题

以下为课上实战例题

第 3 课 哈希表、集合、映射

无序集合、映射

• 1.两数之和

（Easy）半年内出题频次：

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

• 874.模拟行走机器人

（Medium）半年内出题频次：

func robotSim(commands []int, obstacles [][]int) (ans int) {
    // 注意方向数组定义
    dx := []int{0, 1, 0, -1}
    dy := []int{1, 0, -1, 0}
    h := map[int64]bool{}
    for _, obstacle := range obstacles {
        h[calcHash(obstacle[0], obstacle[1])] = true
    }
    x, y, di := 0, 0, 0
    for _, command := range commands {
        if command == -2 {
            di = (di + 3) % 4
        } else if command == -1 {
            di = (di + 1) % 4
        } else {
            // 模拟新增
            for i := 1; i <= command; i++ {
                nx, ny := x + dx[di], y + dy[di]
                if !h[calcHash(nx, ny)] {
                    x, y = nx, ny
                    ans = max(ans, x * x + y * y)
                }
            }
        }
    }
    return ans
}

func calcHash(x, y int) int64 {
    // fmt.Sprintf("%d,%d", x, y)
    // [2]int{x, y}
	return int64(x + 30000) * 60001 + int64(y) + 30000
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

• 49.字母异位词分组

（Medium）半年内出题频次：

// 方法一：排序后做hash key
func groupAnagrams(strs []string) (ans [][]string) {
    mp := map[string][]string{}
    for _, str := range strs {
        strb := []byte(str)
        sort.Slice(strb, func (i, j int) bool {return strb[i] < strb[j]})
        nstr := string(strb)
        mp[nstr] = append(mp[nstr], str)
    }
    for _, words := range mp {
        ans = append(ans, words)
    }
    return ans
}

// 方法二：key [26]int
func groupAnagrams(strs []string) [][]string {
    mp := map[[26]int][]string{}
    for _, str := range strs {
        cnt := [26]int{}
        for _, c := range str {
            cnt[c - 'a']++
        }
        mp[cnt] = append(mp[cnt], str)
    }
    ans := [][]string{}
    for _, v := range mp {
        ans = append(ans, v)
    }
    return ans
}

• 30.串联所有单词的子串

（Hard）半年内出题频次：

// 高效算法
func findSubstring(s string, words []string) (res []int) {
	if len(words) < 1 {
		return 
	}

	slen := len(s)
	wlen := len(words)
	k := len(words[0])
	if slen < k*wlen {
		return 
	}

    mp := map[string]int{}
	for _, w := range words {
		mp[w]++
	}

	// 移动窗口减少重复检查单词，按单词长度取不同批次
	for i := 0; i < k; i++ {
        countermp, count := map[string]int{}, 0
		for l, r := i, i; r <= slen-k; r = r + k {
			word := s[r : r+k]
			if num, found := mp[word]; found {
				// 如果计数器中单词数目超标，左移指针直至符合数目要求
				for countermp[word] >= num {
					countermp[s[l:l+k]]--
					count--
					l += k
				}
				countermp[word]++
				count++
				// fmt.Println(countermp, count)
			} else {
				// 如果当前单词不在词典里，左移指针至下一个单词，左移过程中清理计数
				for l < r {
					countermp[s[l:l+k]]--
					count--
					l += k
				}
                // 此时l = r
				l += k
			}
			if count == wlen {
				res = append(res, l)
			}
		}
	}
	return res
}

// c++方法一写法翻译
func findSubstring(s string, words []string) (ans []int) {
    search := map[string]int{}
    for _, word := range words {
        search[word]++
    }
    n, m, size := len(s), len(words), len(words[0])
    for i, j := 0, 0; i < n - m * size + 1; i++ {
        sub := map[string]int{}
        for j = 0; j < m; j++ {
            idx := i + j * size
            word := s[idx:idx+size]
            if _, ok := search[word]; !ok {
                break
            }
            sub[word]++
            if sub[word] > search[word] {
                break
            }
        }
        if j == m {
            ans = append(ans, i)
        }
    }
    return ans
}
// 方法三：	2022/02/23 23:35 时间提交

// 方法一：
class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> res; // 结果
        unordered_map<string, int> search;
        for (auto &word : words) ++search[word]; // 参照物初始化
        int n = s.size(), m = words.size(), len = words[0].size(); // 获取隐藏变量
        for (int i = 0, j = 0; i < n - m * len + 1; ++i) { // 主逻辑
            unordered_map<string, int> sub; // 子字符 查找的中间结果
            for (j = 0; j < m; ++j) { // 子字符串查找逻辑
                auto word = s.substr(i + j * len, len); // 获取子串
                if (!search.count(word)) break; // 子串 不在 words 里面
                if (++sub[word] > search[word]) break; // 子串个数 比 words 多
            }
            if (j == m) res.push_back(i); // 完全匹配
        }
        return res;
    }
};

// 训练营老师写法
class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        int tot = 0;
        for (string& word : words) {
            tot += word.length();
            wordsMap[word]++;
        }
        vector<int> ans;
        for (int i = 0; i + tot <= s.length(); i++) {
            if (valid(s.substr(i, tot), words)) {
                ans.push_back(i);
            }
        }
        return ans;
    }
private:
    bool valid(string str, vector<string>&words) {
        int k = words[0].length();
        unordered_map<string, int> splitWordsMap;
        for (int i = 0; i < str.length(); i += k) {
            splitWordsMap[str.substr(i, k)]++;
        }
        return equalsMap(splitWordsMap, wordsMap);
    }
    bool equalsMap(unordered_map<string, int>& a, unordered_map<string, int>& b) {
        for (auto & key_and_value : a) {
            const string& key = key_and_value.first;
            int value = key_and_value.second;
            if (b.find(key) == b.end() || b[key] != value) return false;
        }

        for (auto & key_and_value : b) {
            const string& key = key_and_value.first;
            int value = key_and_value.second;
            if (a.find(key) == a.end() || a[key] != value)  return false;
        }
        return true;
    }
    unordered_map<string, int> wordsMap;
};

LRU

• 146.LRU 缓存机制

（Medium）半年内出题频次：

type listNode struct {
	Key, Value int
	Pre, Next *listNode
}

type LRUCache struct {
	capacity, cnt int
	h map[int]*listNode
	head, tail *listNode
}

func Constructor(capacity int) LRUCache {
	h := make(map[int]*listNode, capacity)
	head, tail := &listNode{}, &listNode{}
	head.Next = tail
	tail.Pre = head
	return LRUCache{
        capacity:capacity,
        h:h,
        head:head,
        tail:tail,
    }
}

func (this *LRUCache) Get(key int) int {
	if node, ok := this.h[key]; ok {
		this.removeNode(node)
		this.insertHeadNode(node)
		return node.Value
	}
	return -1
}

func (this *LRUCache) Put(key int, value int)  {
	if node, ok := this.h[key]; ok {
		node.Value = value
		this.removeNode(node)
		this.insertHeadNode(node)
	} else {
		if this.cnt == this.capacity {
			node = this.tail.Pre
			this.removeNode(this.tail.Pre)
			delete(this.h, node.Key)
			this.cnt--
		}
		node = &listNode{Key: key, Value: value}
		this.insertHeadNode(node)
		this.h[key] = node
		this.cnt++
	}
}

func (this *LRUCache) removeNode(node *listNode) {
	node.Next.Pre = node.Pre
	node.Pre.Next = node.Next
}

func (this *LRUCache) insertHeadNode(node *listNode) {
	this.head.Next.Pre, node.Next = node, this.head.Next
	this.head.Next, node.Pre = node, this.head
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */

第 4 课 前缀和、差分、双指针扫描

前缀和、差分

• 1248.统计「优美子数组」

（Medium）半年内出题频次：

// 训练营
func numberOfSubarrays(nums []int, k int) (ans int) {
    n := len(nums)
    s := make([]int, n + 1)
    for i := 1; i <= n; i++ {
        s[i] = s[i-1] + nums[i-1] & 1
    }
    cnt := make([]int, n + 1)
    cnt[s[0]]++
    for i := 1; i <= n; i++ {
        if s[i] - k >= 0 {
            ans += cnt[s[i] - k]
        }
        cnt[s[i]]++
    }
    return ans
}

// 官方
func numberOfSubarrays(nums []int, k int) int {
    n := len(nums)
    cnt := make([]int, n + 1)
    odd, ans := 0, 0
    cnt[0] = 1
    for i := 0; i < n; i++ {
        odd += nums[i] & 1
        if odd >= k {
            ans += cnt[odd-k]
        }
        cnt[odd]++
    }
    return ans
}

• 53.最大子序和

（Easy）半年内出题频次：

// 前缀和 + 前缀最小值
func maxSubArray(nums []int) int {
    n := len(nums)
    s := make([]int, n + 1)
    preMin := make([]int, n + 1)
    for i := 1; i <= n; i++ {
        s[i] = s[i-1] + nums[i-1]
    }
    preMin[0] = s[0]
    for i := 1; i <= n; i++ {
        preMin[i] = min(preMin[i-1], s[i])
    }
    ans := math.MinInt32
    for i := 1; i <= n; i++ {
        if ans < s[i] - preMin[i-1] {
            ans = s[i] - preMin[i-1]
        }
    }
    return ans
}
func min(a, b int) int{
    if a < b {
        return a
    }
    return b
}

// 贪心
func maxSubArray(nums []int) int {
    sum, ans, n := 0, math.MinInt32, len(nums)
    for i := 0; i < n; i++ {
        sum += nums[i]
        if ans < sum {
            ans = sum
        }
        if sum < 0 {
            sum = 0
        }
    }
    return ans
}

// 动态规划: 
// 标准dp
func maxSubArray(nums []int) int {
    ans, n := nums[0], len(nums)
    dp := make([]int, n)
    dp[0] = nums[0]
    for i := 1; i < n; i++ {
        dp[i] = max(0, dp[i-1]) + nums[i]
        ans = max(ans, dp[i])
    }
    return ans
}
// 简化dp
func maxSubArray(nums []int) int {
    ans, pre, n := nums[0], nums[0], len(nums)
    for i := 1; i < n; i++ {
        pre = max(0, pre) + nums[i]
        if pre > ans {
            ans = pre
        }
    }
    return ans
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

• 304.二维区域和检索 - 矩阵不可变

（Medium）半年内出题频次：

type NumMatrix struct {
    sum [][]int
}

func Constructor(matrix [][]int) NumMatrix {
    m, n := len(matrix), len(matrix[0])
    sum := make([][]int, m + 1)
    sum[0] = make([]int, n + 1)
    for i := 1; i <= m; i++ {
        sum[i] = make([]int, n + 1)
        for j := 1; j <= n; j++ {
            sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + matrix[i-1][j-1]
        }
    }
    return NumMatrix{sum}
}

func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
    sum := this.sum
    return sum[row2+1][col2+1] - sum[row2+1][col1] - sum[row1][col2+1] + sum[row1][col1]
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * obj := Constructor(matrix);
 * param_1 := obj.SumRegion(row1,col1,row2,col2);
 */

// 写法二
type NumMatrix struct {
    sums [][]int
}

func Constructor(matrix [][]int) NumMatrix {
    m := len(matrix)
    if m == 0 {
        return NumMatrix{}
    }
    n := len(matrix[0])
    sums := make([][]int, m+1)
    sums[0] = make([]int, n+1)
    for i, row := range matrix {
        sums[i+1] = make([]int, n+1)
        for j, v := range row {
            sums[i+1][j+1] = sums[i+1][j] + sums[i][j+1] - sums[i][j] + v
        }
    }
    return NumMatrix{sums}
}

func (nm *NumMatrix) SumRegion(row1, col1, row2, col2 int) int {
    return nm.sums[row2+1][col2+1] - nm.sums[row1][col2+1] - nm.sums[row2+1][col1] + nm.sums[row1][col1]
}

• 1109.航班预订统计

（Medium）半年内出题频次：

// 差分思想
func corpFlightBookings(bookings [][]int, n int) []int {
    delta := make([]int, n + 2)
    for _, booking := range bookings {
        first, last, seats := booking[0], booking[1], booking[2]
        delta[first] += seats
        delta[last+1] -= seats
    }
    ans := make([]int, n + 1)
    for i := 1; i <= n; i++ {
        ans[i] = ans[i-1] + delta[i] 
    }
    return ans[1:]
}

// 官方题解，更简洁，单理解稍难
func corpFlightBookings(bookings [][]int, n int) []int {
    nums := make([]int, n)
    for _, booking := range bookings {
        first, last, seats := booking[0], booking[1], booking[2]
        nums[first-1] += seats
        if last < n {
            delta[last] -= seats
        }
    }
    for i := 1; i < n; i++ {
        nums[i] += nums[i-1]
    }
    return nums
}

双指针扫描、滑动窗口

• 1.两数之和

（Easy）半年内出题频次：

// 训练营写法go版本
type pair struct{x, y int}
func twoSum(numbers []int, target int) []int {
    pairs := []pair{}
    // 构造 type pair struct{x, y int} slice
    for i, num := range numbers {
        pairs = append(pairs, pair{i, num})
    }
    // 对 slice 排序
    sort.Slice(pairs, func (i, j int) bool {
        return pairs[i].y < pairs[j].y
    })
    // 双指针
    j := len(numbers) - 1
    for i := 0; i < j; i++ {
        for i < j && pairs[i].y + pairs[j].y > target { j-- }
        if i < j && pairs[i].y + pairs[j].y == target {
            return []int{pairs[i].x, pairs[j].x}
        }
    }
    return nil
}

• 167.两数之和 II - 输入有序数组

（Easy）半年内出题频次：

// 双指针
func twoSum(numbers []int, target int) []int {
    left, right := 0, len(numbers)-1
    for left < right {
        sum := numbers[left] + numbers[right]
        if sum == target {
            return []int{left+1, right+1}
        } else if sum < target {
            left++
        } else {
            right--
        }
    }
    return nil
}

// 训练营写法go版本
func twoSum(numbers []int, target int) []int {
    j := len(numbers) - 1
    for i := 0; i < j; i++ {
        for i < j && numbers[i] + numbers[j] > target { j-- }
        if i < j && numbers[i] + numbers[j] == target {
            return []int{i+1, j+1}
        }
    }
    return nil
}

• 15.三数之和

（Medium）半年内出题频次：

func threeSum(nums []int) (ans [][]int) {
    sort.Ints(nums)
    n := len(nums)
    for i := 0; i < n - 2; i++ {
        if i > 0 && nums[i-1] == nums[i] {
            continue
        }
        for j, k := i + 1, n - 1; j < k; {
            sum := nums[i] + nums[j] + nums[k]
            if sum < 0 {
                for j++; j < k && nums[j-1] == nums[j]; j++ {}
            } else if sum > 0 {
                for k--; j < k && nums[k+1] == nums[k]; k-- {}
            } else {
                ans = append(ans, []int{nums[i], nums[j], nums[k]})
                for j++; j < k && nums[j-1] == nums[j]; j++ {}
                for k--; j < k && nums[k+1] == nums[k]; k-- {}
            }
        }
    }
    return ans
}

• 11.盛最多水的容器

（Medium）半年内出题频次：

func maxArea(height []int) (ans int) {
    i, j := 0, len(height) - 1
    for i < j {
        if height[i] < height[j] {
            ans = max(ans, (j-i) * height[i])
            i++
        } else {
            ans = max(ans, (j-i) * height[j])
            j--
        }
    }
    return ans
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}