前情提要本文是个人学习的粗糙笔记，仅记录思路和图解（跳过了困难题，等之后再弄）视频看的是油管上的neetcode哈希 3哈希表的优点，查询时间复杂度低、可去重、键-唯一、值-链表或红黑树两数之和(简单，HashMap)两种解法的图示：哈希表思路：遍历，键是数组元素，值是数组索引 检查哈希表里是否有对应的数值，有则返回两个索引，否则存储数据和索引 ​​​​​​containsKey(key)，是否含有对应的键，检查哈希表中是否存在所需数值 put(key，value)，存放数据和索引 get(key)，返回value，即数组索引字母异位词分组（HashMap）综合思路：哈希表的键是同一组字母异位词的标志 哈希表的值是一组字母异位词列表哈希表的键：字符串——字符数组——排序——新字符串，即排序后的字符串 长度为26的数组记录每个字母出现次数 根据该数组将出现的字母和出现次数按顺序拼接成字符串哈希表的值：对应的异位词列表，添加字符串到该列表中更新哈希表的键值对返回哈希表中所有的值最长连续序列(HashSet)思路如下：哈希表——所有数字存入哈希表中，唯一性可去重，add(num)序列起始点——遍历哈希表，寻找序列起始点，contains(num)序列长度——从起始点向后扩展计算序列长度，维护并更新最大序列长度双指针 7移动零（简单）nums[r]==0的话是把0移动到前面去了，而不是数组后面盛最多水的容器三数之和(ArrayList)三个数字不等、保证L在R左边a，判断排序后第一个元素、重l和r三种情况接雨水(困难)两种方法滑动窗口 9无重复字符的最长子串（HashSet）哈希集合来存储滑动窗口包含的字符l遍历；r从左往右滑动找到字符串中所有字母异位词思路一：比较的内容是统计S中Plength长度和P中字符出现次数初始化窗口——滑动，左删右增，利用count的减加实现——判断S和P的count是否相等以便记录初始索引字符串提取元素用charAt(i)思路二：只用一个count初始化窗口，S增P减，用differ记录conut不为0的个数——滑动，左删右增，利用count的减加实现；需根据count的数值进行differ的加减——根据differ是否为0进行初始索引的记录charAt()​​：用于从字符串中提取特定位置的字符，核心是​​索引访问​​。​​toChar()​​：用于将其他类型（如整数、Unicode）转换为字符，核心是​​类型转换​​。子串 12和为k的子数组思路一 暴力枚举两个for循环：一个for遍历数组 一个for从遍历的本轮次索引向更小的索引方向进行求和，为k则加1思路二 前缀和一个hashmap，键是前缀和（prefix sum）的值，值是该前缀和出现的次数一个for循环，遍历数组一个判断，前缀和之差是否为k初始化哈希表为（0，1），目的是为了防止没有前缀和为0的记录，导致k刚好为前几个元素和的子串没有相关记录，以便统计那些从数组开头就满足条件的子数组。滑动窗口最大值（困难）思路一 优先队列优先队列：存储元素值和对应索引，按照值降序排列初始化窗口，第一个窗口最大值遍历后续窗口，先加入新元素、再移出不在当前窗口的最大值、然后求最大值pq.peek()是优先队列的方法，用于查看队首元素pq.peek()[0]：获取队首元素的值（nums[i]）pq.peek()[1]：获取队首元素的索引（i）思路二 双端队列 Deque双端队列：存储的是元素的索引，保持队列中的索引对应的值是递减的初始化窗口，第一个窗口最大值遍历后续窗口，先移出队列中所有小于当前元素的索引，再加入当前元素，然后移出不在当前窗口的元素索引，最后最大值是队列头部元素对应的值思路三 分块+预处理prefixMax前缀最大值数组suffixMax后缀最大值数组每个窗口最大值是在suffixMax[i], prefixMax[i + k - 1]中取最大最小覆盖子串（困难）思路：滑动窗口+哈希表t的字符次数哈希表——初始化滑动窗口——判断窗口是否满足条件，即当前窗口和t的哈希表的比较，字符个数、次数——主循环滑动窗口，先右指针右移，再添加新元素，然后检查判断是否进行窗口收缩——返回子串普通数组 17