最近在准备找工作,刷了 LeetCode 一百多题,还在入门阶段。在学习新的解题技巧的同时,准备写一个系列总结归纳自己碰到过的刷题套路和思考,作为对自己学习过程的记录。
由于自己主要找前端开发,并且对 JS 比较熟悉,刷题语言采用 JS。
目前笔记结构还比较混乱,会随着刷题进程不断完善。
全系列文章也可访问这里
Arrays 数组
常需要遍历。下述方法也多适用于需要遍历的字符串有关问题。
for 循环
每循环一层时间复杂度便增加一个量级。 技巧:使用Hashmap,查找时间复杂度为 O(1),占用 O(n) 空间
例: (Two Sum) [leetcode.com/problems/tw…]
var twoSum = function (nums, target) {
let record = new Map();
for (const [index, num] of nums.entries()) {
let compliment = target - num;
// if found the pair
if (record.has(compliment)) { // 如果找到了 compliment (说明之前存过),则返回两个坐标
return [record.get(compliment), index];
}
record.set(num, index); // 如果没找到,则记录当前数的位置,以便之后查找
}
};
双指针
使用两个指针对数组进行遍历。 时间复杂度为 O(n)。 通常需要一个判断条件来决定如何移动指针。
常见条件:
- 升序排序数组,可根据目标值与当前值大小决定,小于目标值则左指针右移,反之则右指针左移。
- LeetCode Prob.15 3Sum: 求总和为零
- 可能对目标值的影响
- LeetCode Prob.11 Container with Most Water: 目标值为面积,可根据如何移动可能会使面积更大来判断
使用场景
- 回文字符子串
- LeetCode Prob.5 Longest Palindromic Substring: 对于每一个位置,从该位置开始两个指针分别向左向右移动,找到最长的回文子串
- LeetCode Prob.647 Palindromic Substrings: 对于每一个位置,从该位置开始(或该位置及其相邻位置开始,或及其隔位开始)两个指针分别向左向右移动,只要相等则回文子串总数加一
- 找一对数,尤其数组排好序后
- 如果是找更多的数可以拆解成一个数加一对数
- 若数组未排序,在不损失时间复杂度的情况下也可以考虑将数组排序