数组题

1.剑指 Offer 40. 最小的k个数

剑指 Offer 40. 最小的k个数 - 力扣（LeetCode） (leetcode-cn.com)
没优化之前，一直递归，没有缩小范围：二分的本质，缩小范围

最快优化：巧用if else，二分思想

2.485. 最大连续 1 的个数

https://leetcode-cn.com/problems/max-consecutive-ones/

注意：方法里的数如何在外边返回，c = Math.max(c , count);

如何优化？之前是每次都比一次，发现=1时不用比，=0时比一次，不要忘了最后没有0，也要再比一次！！！！

3.704二分查找！（排好序找数就是二分）

二分思想连接讲解：https://leetcode-cn.com/circle/discuss/dZ4Cj5/
704. 二分查找 - 力扣（LeetCode） (leetcode-cn.com)
暴力不用二分，没有缩小范围！

二分要用while循环，注意大小于号别反就OK

4.移除元素

27. 移除元素 - 力扣（LeetCode） (leetcode-cn.com)
前后指针法：只要有用部分，遇到val快指针就走，否则i++并取j值

5.有序数组的平方

977. 有序数组的平方 - 力扣（LeetCode） (leetcode-cn.com)
方法一：直接计算排序比较

快排写法，也不快！

方法二： 优化：双指针，前后指针一定要注意创建新数组用新指针，防止太乱
归并思路，归并只适合两个不同有序数组合并，双指针！
合并两个有序数组！归并思想 创建新数组接收！

经典问题

经典问题：1. 两数之和

巧用hash表记录索引，实现o（1）复杂度

经典问题：2.用两个栈实现队列

经典问题：3. 合并两个有序链表

一定注意细节！！！

经典问题：4.二叉树的中序遍历

非递归迭代实现 （用栈模拟递归）

经典问题：5. 反转链表

注意while条件

递归注意一定要置null防止成环！！！

经典问题：6.有效的回文

注意细节！！！

经典问题：7. 回文链表（两种方法）

1复制数组加双指针

1. 反转中间结点链表作比较

经典问题：8. 回文数

（整数转字符串）

经典问题：9.二叉树的前后中序遍历

难点：后序遍历
注意设置null值 然后回补！！！
为何要设置储存节点，防止超时？

经典问题：10.二叉树的最小深度

防止出现单链表情况发生！！！！
记住这个特例是5！！！

经典问题：11相同的树

注意if，else if，else的使用！！！！（第一步很巧妙，解决很多问题！！）

经典问题：12路径总和

一定要先判断，后减！！！！

经典问题：13.二叉树的最近公共祖先

注意细节，和情况分析！！！

经典问题：14二叉搜索树的最近公共祖先

自己写的，巧妙用val比较增加速度！！！

经典问题：15翻转二叉树

树如果改变结构的话，动的一定是指针！！而不是数值！！！

经典问题：16. 二叉树的直径

经典问题：17. 合并二叉树

经典问题：18.x 的平方根

二分查找！！注意细节！！防越界 //右移一位相当于除2，右移n位相当于除以2的n次方。

经典问题：19.反转链表 II

经典问题：20. 链表中倒数第k个节点

快慢指针：

遍历法：

经典问题：21. 有效的括号

注意细节，逻辑！！也可改

经典问题：22. 移动零

双指针！！

经典问题：23. 汉明距离

二进制用&1移位计数！！

经典问题：24. 爬楼梯

巧妙规律计算，也可递归，超时！！！

经典问题：25. 找到所有数组中消失的数字

HashSet去重，效率低

经典问题：26. 比特位计数

直接模拟找规律！！！

经典问题：27. 最小栈

经典问题：28. 买卖股票的最佳时机

简单容易想到的动态规划！！（注意实现）

滑动窗口算法总结

场景：

• 滑动窗口算法可以用以解决数组/字符串的子元素问题，例如最大，最小长度
• 滑动窗口算法可以将嵌套的for循环问题，转换为单循环问题，降低时间复杂度

步骤：第一步：找到窗口大小条件，大小一定是不变的，一定用right-left+1
第二步：如果窗口大了怎么减小？首先指针增大，然后总数要减去前边的窗口外的数
第三步：一定注意是先删除，后比较，否则还没删就比较就不对了
重难点：i与j的处理！！！ j到底能不能加1的问题

1. 长度最小的子数组

暴力循环：注意细节

因为这道题保证了数组中每个元素都为正，所以前缀和一定是递增的，这一点保证了二分的正确性。如果题目没有说明数组中每个元素都为正，这里就不能使用二分来查找这个位置了

有序数组查找，用二分
滑动窗口算法
在本题中实现滑动窗口，主要确定如下三点：

• 窗口内是什么？
• 如何移动窗口的起始位置？
• 如何移动窗口的结束位置？

窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。
窗口的起始位置如何移动：如果当前窗口的值大于s了，窗口就要向前移动了（也就是该缩小了）。
窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，窗口的起始位置设置为数组的起始位置就可以了。
注意while使用，因为删除一个还可能大于target，要继续删，而且j不能动
也可改成while

2 存在重复元素 II

滑动窗口
// 滑 -> 扩大窗口 缩小窗口的时机
// 记 -> 使用什么数据结构，什么时候记忆
（用set少一个j++，先判断后加，）

用set少一个j++，先判断后加，否则卡死在0；

• 窗口内是什么？
• 如何移动窗口的起始位置？
• 如何移动窗口的结束位置？
• 用hashSet去重，重点控制窗口大小和窗口太大如何删除！由题意！！！
• 
• 
• 

3.最长不含重复字符的子字符串

https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/


字符串一定要注意空格的问题，放上边比较
什么时候删除，什么时候比较，别忘了添加！

4.子数组最大平均数 I

https://leetcode-cn.com/problems/maximum-average-subarray-i/
错误版，末端可能是大负数，因为比的是j+1！！！

解决：j缩小，k = j - i +1;每次多加最后一个k

5. 找到字符串中所有字母异位词

滑动窗口重难点：窗口大了要删除？如何删除？先删除，后比较，否则s1的值没变就比较了
你这里不是s1里面的值变了呀，第二个if又用到两个比较，然后才add。两个颠倒肯定不一样了呀@凤求凰 
If顺序不要颠倒！！！！

前缀和

什么场景可以用前缀和？（待回答）

场景：1.求左右下标一段之和

1. 求和为多少多少的
2. 前缀和与hashmap连用时注意，必须想其办法让k为0；

1.左右两边子数组的和相等

注意经典前缀和公式，注意从1开始，长度是n+1

1 一维数组的动态和

直接原地修改即可！

巧用sum变量代替前一个下标的数！！！！

2 区域和检索 - 数组不可变

4.找到最高海拔

经典前缀和（注意小细节的处理）

5. 和为 K 的子数组

经典前缀和，巧用map.getOrDefault(pre[i],0)+1 方法，注意先判断，后添加
相当于此方法

长度最小子数组（前缀和实现一定注意顺序!!!!）

3 0 和 1 个数相同的子数组

前缀和与hashmap连用时注意，必须想其办法让k为0；

全排列

1. 全排列

注意递归走法和if范围，还有boolean数组作用，Java只有值传递

2. 全排列 II

一定要注意细节！！！排序+同层去重还是同列去重

重点知识：

异或 ：相同为1，不同为0； A^B

与操作 有0为0，全1为1 A&B

-3 & 5　即 1111 1101
0000 0101
&0000 0101
清零作用，奇数偶数判断

或操作 有1为1，全0为0 A|B

0|0=0； 0|1=1； 1|0=1； 1|1=1；

中等进阶

问题1： 最长回文子串

字符串中心扩散法 注意细节！！！！

问题2：回文子串

中心扩散法：注意奇数偶数判断，偶数两个中心点

问题3：最长连续序列

问题4：环形链表 II

问题5：下一个排列

模拟找规律

自己写的遇到新问题

问题6： 删除链表的倒数第 N 个结点