e# Leetcode
26. 删除排序数组中的重复项
题意：
- 就地修改
- 要求空间占用 O(1)，不能用中间数组
思路：
- 双指针覆写，慢指针在元素不重复时才移动
- 重点不是 nums 修改，而是输出 length。结合 length，可以作一次 slice，给出 nums
- 倒序遍历，当元素重复时，删除当前项
- 正序剪切，会影响 i。倒序减切掉一个元素，i--，不影响待处理元素（身后）
70. 爬楼梯
转化：到达前一步楼梯的方法数+前两步方法数
递归实现：
- 优点： 直接利用问题的递推关系，思路直观。
- 缺点： 时间复杂度是指数级的 O(2n)O(2^n)O(2n)，因为存在大量的重复计算，效率较低，可能导致栈溢出。
带缓存的递归（动态规划）：
- 优点： 通过记录每一步的结果，可以避免重复计算，将时间复杂度降到 O(n)O(n)O(n)。
- 缺点： 需要额外的空间来存储每一步的结果，空间复杂度是 O(n)O(n)O(n)。
空间优化的动态规划：
- 优点： 只需要两个变量来存储前两步的结果，可以将空间复杂度降到 O(1)O(1)O(1)。
- 缺点： 实现稍微复杂一些，但在大多数情况下是最优的解决方案。
动态规划记录每个子问题的解来避免重复计算，通常用于优化递归解决方案。
121. 买卖股票的最佳时机
题意：
- 价格不会为负
思路：
- 模拟抄底，记录到目前为止最低价
- 如果希望知道哪天买入和卖出，可用双指针，慢指针总是指向最小价格
注意点：
- 给
Math.max方法传入太大的数组，会导致超时，解决技巧，遍历时更新最小值 - 从第 2 个价格开始才能计算价格差，初始化最小价格为第一个价格
3. 无重复字符的最长子串
思路：
- 滑动窗口，更新记录最大长度
- 用 Set 维护一个窗口，窗口右边界从 -1 开始
- 连续的重复字符，左边界需要持续移动（while）
拓展：包含所有字母的最小子串（代码量较大）
387. 字符串中的第一个唯一字符
思路：
- 暴力，O(n^2)
- 两次循环，时间 O(n)
- 由于 map 中没有存索引，第二次循环还是遍历原数组，以输出索引
88. 合并两个有序数组
思路：
- 双指针，倒序取较大值，当 nums2 取空时，结束。 case 要考虑全，如 p1 == -1 p2 == -1
896. 单调数列
思路：
- 一次遍历，否定判断，输出一个为真或全部为真 实战：需要特殊技巧，提示后可写出
LCP 06. 拿硬币
公式：f(x) = x / 2 + x % 2
680. 验证回文字符串 Ⅱ
依赖知识：如何判断回文，1. 反转 2. 双指针 3. 迭代
回文指针末尾，lr 相邻，或 l === r，后者只剩一个字母，满足回文，比不比较都行
贪心算法
215. 数组中的第K个最大元素
- sort 降序后，取第 k - 1 元素 O(nlogn)
209. 长度最小的子数组
滑动窗口
- 右边界移动，直到找到解
- 找到解，左边界移动
1143. 最长公共子序列
dp 使用二维数组记录结果
边界，一侧为空字串
dp 方程
js
if (a === b) {
table[row][col] = table[row - 1][col - 1] + 1;
} else {
table[row][col] = Math.max(table[row][col - 1], table[row - 1][col]);
}
关联题目：583. 两个字符串的删除操作
三数之和
- 暴力 O n^3
- 双指针 如何做到不重复（有序 + 有两个数字不重复，第三个数字一定不重复，不会出现 [1, 2]，[2, 1]，每个数字开头的解要穷举）
js
function threeSum(nums, target = 0) {
// let res = []
let res: number[][] = []
nums.sort((a, b) => a - b)
for (let i = 0; i < nums.length; i++) {
if (i > 0 && nums[i] === nums[i - 1]) continue
let l = i + 1
let r = nums.length - 1
while(l < r) {
let other = target - nums[i]
let sum = nums[l] + nums[r]
if (sum > other) r--
if (sum < other) l++
if (sum === other) {
res.push([nums[i], nums[l], nums[r]])
if (l < r && nums[l + 1] === nums[l]) { // 下一个值与当前值相同时，多跳一步
l+=2
} else {
l++
}
}
}
}
return res
}
console.log(threeSum([-1, -2, 2, -2, 0, 4, 1]))
console.log(threeSum([0, 0, 0, 0]))