📝 面试准备 - 算法篇 🌀
记录为面试准备的算法相关内容。
数据结构
基础
常见数据结构
数组
最基础的数据结构。
常考点：
- 找数组中第k大的数字
- 找两个有序数组的中位数
Question:
Leetcode 1: Two Sum 两数之和 [简单] Leetcode 243: Shortest Word Distance 最短单词距离 [简单]
链表
常考点：
- 反转链表
- 链表元素排序
- 合并两个有序链表
- 判断链表是否有环（有环的起始点）
栈
队列
哈希表
树
二叉树
递归思想的数据结构。
常考点：
- 判断二叉树是否平衡
- 判断二叉树是否相同
- 判断二叉树是否对称
图
堆
算法
基础
时间复杂度 常用：大O表示法。
空间复杂度
常见算法思想
- 分治
- 动态规划
- 贪心
- 回溯
- 双指针
常用算法
排序
搜索
动态规划
贪心算法
回溯算法
分治算法
双指针 Two Pointers
双指针算法是一种通过维护两个索引（或指针）来解决问题的技术，这些指针通常从数组或字符串的两端开始，根据特定条件向中间移动。
这种方法在排序数组中寻找满足条件的元素对时特别有效，例如寻找和为目标值的两个数。
核心思想：
通过维护两个索引（或指针）来高效地遍历数据结构，减少时间复杂度，通常达到 O(n)
分为：
标准双指针
适用于排序数组，指针从两端开始，根据元素和与目标值的比较移动。
例如，在“两数之和II-输入有序数组”（LeetCode #167）中，初始化一个指针在数组开头，另一个在结尾，调整指针直到找到目标和。典型例题：
- leetcode: 167. Two Sum II - Input Array Is Sorted
- leetcode: 15. 3Sum
- leetcode: 18. 4Sum
- leetcode: 11. Container With Most Water
- leetcode: 75. Sort Colors
- leetcode: 283. Move Zeroes
- leetcode: 26. Remove Duplicates from Sorted Array
复杂度：
- 时间：O(n)
- 空间：O(1)
滑动窗口
一种高级双指针变体，用于子数组或子串问题，通过两个指针定义一个窗口，扩展或收缩窗口以满足条件。
例如，“最长不含重复字符的子串”（LeetCode #3）使用滑动窗口找到最长无重复字符的子串。典型例题：
- leetcode: 3. Longest Substring Without Repeating Characters
- leetcode: 76. Minimum Window Substring
复杂度：
- 时间：O(n)
- 空间：O(k),k为窗口内可能包含的唯一元素数
快慢指针
主要用于链表问题，如检测循环（Floyd 循环检测算法）。快指针每次移动两步，慢指针移动一步，若快指针到达空或相遇则无环，否则有环。
例如，“链表是否有环”（LeetCode #141）中，快指针每次移动两步，慢指针移动一步，如果有环它们会相遇。典型例题：
- leetcode: 141. Linked List Cycle
- leetcode: 876. Middle of the Linked List
复杂度：
- 时间：O(n)
- 空间：O(1)