hot100思路总结

Posted on In , Views:
记一下hot100的思路

Hot100

哈希

  1. 两数之和

遍历同时用map记录已经遍历过的元素

  1. 字母异位词分组

单词字典排序作为key，原单词作为value，最后取出map中的value作为切片

  1. 最长连续序列

map记录每个数，遍历map，从最小的数开始找记录长度

双指针

  1. 移动零

同向双指针，一个遍历元素，一个标记非零元素

  1. 盛最多水的容器

相向双指针，接水问题，高度由较短的一边决定

  1. 三数之和

排序，固定一个数后还是两数之和，相向双指针，关键是注意去重

  1. 接雨水

一个位置一个桶，一个桶两个边，桶盛水量由“前后缀的较小方决定”。每次更新左右其中一个桶，相向双指针

滑动窗口

  1. 无重复字符的最长子串（耐考王）

map记录子串元素出现次数，同向双指针->只出现一次

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

map记录目标元素出现次数，同向双指针->和目标元素出现次数一致

子串

  1. 和为 K 的子数组

子数组和问题->前缀和的差，用map记录前缀出现次数