Algorithms / LeetCode
算法刷题模型整理（二）
按链表、数组、哈希表、字符串等主题整理常见题型、核心思路和易错点。
LC027 移除元素
解题模型：
双指针
核心思路：
- 头尾指针，left命中就把right的值复制到left，然后right左移，left未命中则右移，加起来只用遍历一遍数组，但是会打乱顺序
- 快慢指针，left和right同时从0出发，检查right是否命中，未命中则复制到left，然后后移left和right，命中则只后移right，能保持顺序，但有可能遍历两遍数组
易错点：
- 边界条件
- 无需交换，可以直接把后面要保留的值复制到前面
LC977 有序数组的平方
解题模型：
双指针
核心思路：
头尾指针，比较left和right的绝对值，大的一个平方过后逆序放入答案数组
易错点：
- 题目概念，非递减——非严格递增，每一项都>=前面一项
- 注意逆序放入答案数组
- 数据特征是对称的，即平方后两边大中间小，所以可以考虑头尾指针
LC209 长度最小的子数组
解题模型：
滑动窗口
核心思路：
用left和right维护一个窗口，同时从下标0出发，
右移right直到符合要求，更新最小长度，然后left后移直到不符合，
一直重复这个过程直到right到达尾部
易错点：
- 滑动窗口的理解
LC015 三数之和
解题模型：
排序，双指针
核心思路：
降维：3sum->2sum
先排序，固定一个数first，然后简化为两数之和，目标为-first，期间重复的要跳过，因为排序了，所以重复的都是连在一起的，两数之和直接头尾指针，固定left，左移right直到不再大于目标数，等于就添加到答案，小于就右移left，left和right遇到重复的也要跳过，直到left和right相遇，再改变first，重复
易错点：
- 三处剪枝，1、first不会大于零 2、first和它后面跟着的两个数加起来不会大于0 3、first和最后两个数加起来不会小于0
- 跳过重复的数时只需要比较它和前面一个数是否相等
哈希表
常见问题：
- 数组、unordered_map、map的使用时机
- key的范围小且固定或者是整数、字符时用数组
- 以上条件不符合时，即key范围较大或key比较复杂时用unordered_map
- 若需要元素有序（map特性元素有序存放），范围查找，需要最小、最大则使用map
LC242 有效的字母异位词
解题模型：
字符统计
核心思路：
思路1：先确定长度是否相等，然后哈希表储存每个字符的出现次数，再遍历新串，将遍历到的字符对应出现次数减去1
思路2：对字符串进行排序，若相等则证明是异位词
易错点：
- 开始先检查长度是否相等，若不相等可以直接结束，并且后续无需再检查哈希表是否全部置零，即新串为子串这种情况，因为长度相等，结束时若有一个字符大于零，必有一个小于零
- 这题应该使用数组，因为key的范围小，是字符，这题的进阶为会出现unicode字符，这时就要用unordered_map
LC349 两个数组的交集
解题模型：
去重、存在性判断
核心思路：
思路1：哈希表存数组1每个元素出现情况，然后再遍历数组2，元素出现过的存入答案数组
思路2：将两个数组进行排序，双指针分别指向两个数组的开始位置，同时移动，相等则加入答案数组
易错点：
- 这题使用数组，范围固定，注意的是数组开辟的大小应该是最大元素的值+1，因为元素会作为下标使用
- 注意去重，元素放入答案数组后要把哈希表中对应的出现情况置0，否则数组2再次出现相同元素时会重复放入答案数组
LC001 两数之和
解题模型：
哈希表/双指针
核心思路：
思路1：建立哈希表存放值与下标，遍历数组，查找值为目标值-当前值的元素，注意先查再存，这样可以防止重复使用，即在查找时，元素自身还没被存放进表中
思路2：先对元素进行从小到大的排序，头尾指针查找答案，若偏小则右移left，偏大则左移right
易错点：
- 注意不要重复用到元素自身