经典算法题:最长回文子串、无重复最长子串、最大子数组和
哪些公司问过
答案要点
- 无重复最长子串:滑动窗口 + 哈希表记录字符位置,遇到重复就收缩左边界;O(n)
- 最大子数组和:Kadane,cur = max(x, cur + x),ans = max(ans, cur);O(n),空间 O(1)
- 最长回文子串:中心扩展,奇偶两种中心;时间 O(n²),空间 O(1)
- 可提 DP 解法(O(n²) 空间)和 Manacher(O(n))
- 边界:空串、单个字符、全负数数组
易错点
- 滑动窗口收缩时移动左指针错误,导致回退
- Kadane 初始化为 0,全负数数组时结果错误
- 中心扩展只考虑奇数长度的回文
- 只写思路不处理边界
面试官常见追问
- 最大子数组和如果要返回子数组的下标怎么办?
- 最长回文子串的中心扩展为什么要处理奇偶两种情况?
- 滑动窗口什么时候适用?
- 最大子数组和能用分治吗?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 数组和链表的区别与适用场景173 场
- 合并有序数组与合并区间66 场
- 三数之和:排序加双指针50 场
- 字符串相加(大数加法)20 场
- 字符串匹配:KMP 算法18 场
- 字符串反转的实现与注意事项17 场
- 接雨水问题的三种解法14 场
- 螺旋矩阵遍历14 场
- 两数之和的几种解法12 场
- 实现 atoi:字符串转整数11 场