力扣hot100二刷——哈希、双指针、滑动窗口
第二次刷题不在idea写代码，而是直接在leetcode网站上写，“逼”自己掌握常用的函数。
| 标志 | 掌握程度 | 解释 | 办法 |
|---|---|---|---|
| ⭐ | Fully 完全掌握 | 看到题目就有思路，编程也很流利 | |
| ⭐⭐ | Basically 基本掌握 | 需要稍作思考，或者看到提示方法后能解答 | |
| ⭐⭐⭐ | Slightly 稍微掌握 | 需要看之前写过的代码才能想起怎么做 | 多做 |
| ⭐⭐⭐⭐ | absolutely no 完全没有掌握 | 需要看题解才知道怎么做 | 背 |
| ⭐⭐⭐⭐⭐ | 有难度的高频题 | 需要看题解才知道怎么做，而且过几天就忘了这道题怎么做了 | 背背 |
| 序号 | 掌握程度 | 难度 | 类型 | 题号/题名 | 思路/易错点 | 新的函数 |
|---|---|---|---|---|---|---|
| 1 | ⭐ | Easy | 哈希 | 1/两数之和 | 先把每个数保存进map再进行后续操作 的做法是错误的， 因为这样的话，后面map.ContainsKey()找到的数可能是数字本身，而不是另一个数字 所以应该边遍历数组，边查找map中是否只有匹配的元素，然后再添加元素到map， 一句总结：寻找当前元素之前是否有匹配的数 | if(map.containsKey(target - nums[i])) |
| 2 | ⭐⭐ | Medium | 哈希 | 49/字母异位词分组 | 遍历字符串数组 对数组中的每个字符串进行内部的字母排序 相同的字母排序作为同一个键，将排序前的字符串添加进键对应的值（是一个数组） | char[] ch = str.toCharArray(); Arrays.sort(ch); List strList = map.getOrDefault(s, new ArrayList()); map.put(s, strList); |
| 3 | ⭐⭐⭐⭐ | Medium | 哈希 | 128/最长连续序列 | 先遍历一边数组，将数组中元素存进set集合 再次遍历数组 每次遍历中，如果没有当前数前面的那个数，说明可以从该数开始向后寻数（用一个temp记录临时长度），直到找不到连续的数，就结束这次循环 每次遍历，更新答案。 | while(set.contains(num++)) |
| 4 | ⭐⭐ | Easy | 双指针 | 283/移动零 | 一个指针left维护为0的位置，指针right维护不为0的位置 right指针遍历整个数组（right++） 遇到位置left上的数为0，right上的数不为0时就交换位置，left++ | |
| 5 | ⭐ | Medium | 双指针 | 11/盛最多水的容器 | 比较简单 一个指针从数组最左向右移动，一个指针从数组最右向左移动 哪个指针指向的数更小，就移动哪个指针。 | |
| 6 | ⭐⭐⭐ | Medium | 双指针 | 15/三数之和 | 这道题的重点在于避免重复结果 先把数组排序，排序后的第一位数如果大于0，直接return 然后再遍历数组，对数组中的每个数去寻找另外两个数 遍历时，要跳过一样的数（从第二个数开始，和上一个数一样就跳过） 维护两个指针，分别指向当前数的下一个数和数组尾数 While(left < right) 中遍历寻找另外两个数，使这三个数的和为0 在寻找的同时，也一定要注意避免重复的结果，使用while循环来跳过一样的数，且要注意left < right | ans.add(Arrays.asList(nums[i], nums[left], nums[right])); |
| 7 | ⭐⭐⭐ | Hard | 双指针 | 42/接雨水 | 两种解法：一种是前后缀分解，知道思路后其实很简单，另一种是单调栈 前后缀分解需要三次遍历数组。 第一次遍历数组，来维护一个保存每个当前数左边最大的数的数组 第二次遍历数组，来维护一个保存每个当前右边最大的数的数组 第三次遍历数组，来累加每个位置上的积水 | |
| 8 | ⭐ | Medium | 滑动窗口 | 3/无重复字符的最长字串 | 维护一个哈希集合，保存当前子串中的字母 维护左右指针，left、right，分别指向子串头尾 右指针向右移动，同时判断新的字母是否和当前子串集合中的字母重复，如有重复，移动左指针，直到没有重复为止 | set.add(ch[right]); set.remove(ch[right]); |
| 9 | ⭐⭐ | Medium | 滑动窗口 | 438/找到字符串中所有字母异位词 | 维护两个大小为26的字母数组，用来保存当前遍历子串的字母数量，和目标子串的字母数量 维护left、right指针，分别指向当前遍历子串的头尾 判定完当前子串是否是目标字串的异位词后，再将左右指针右移 |
图片版：
