说个我自己的体会。刚开始刷题那会儿我总喜欢追着“高级”算法跑线段树、斜率优化、网络流觉得这才叫算法。结果第一次模拟面试一道“统计数组中逆序对数量”的题把我问住了现场憋了十分钟没写出归并排序的完整代码。那一瞬间我才意识到真正决定基本功下限的恰恰是排序、二分、前缀和与差分、双指针、字符串这五样东西。它们在各类热词榜单里反复出现也是每一轮笔试面试和算法竞赛入门题里几乎必考的组合。这篇文章我想把这五个基础技巧串起来讲一遍。重点不是简单贴模板而是把每个技巧背后的适用场景、常见误区、实战变体讲清楚。无论你是准备面试的应届生、刚接触算法竞赛的初学者还是写业务代码但想补基础的工程师这套内容都值得花一个下午认真过一遍。1. 排序、二分、前缀和差分、双指针、字符串为什么值得放在一起练1.1 它们不是五个孤立知识点而是一条能力链我见过不少同学把算法基础当成“字典式学习”排序背一个模板二分背一个模板前缀和背一个模板然后就开始对着题目发呆。这种学法的最大问题是真题从来不会告诉你“这题用排序”或者“这题用二分”它只给你一个场景需要你自己从工具箱里挑趁手的家伙。这五个技巧恰好构成一条完整的能力链排序是最常用的预处理手段把无序变有序很多问题一旦有序就豁然开朗二分查找依赖有序性直接在有序序列上做快速定位还能把“求最值”问题转化为“判定可行性”问题前缀和与差分处理的是区间统计和区间修改可以看作把“逐个处理”变成“预处理后O(1)查询”双指针利用的是单调性把双重循环降成单趟扫描很多字符串和数组子段问题靠它提速字符串则是前面所有技巧的最佳演练场字符串排序、字符串二分、字符串哈希配合双指针能把前面四样东西全部串起来考试。所以我把它们放在同一篇文章里是因为它们互相成就排序给二分提供舞台前缀和给双指针提供快速区间和字符串又把它们整合到一起。1.2 每类问题的适用场景速查技巧典型信号时间复杂度常见变形排序求第K大、逆序对、区间合并、按某种规则排列O(n log n)稳定性要求、计数排序、自定义比较器二分查找有序数组、求满足条件的最左/最右位置、答案单调O(log n)二分答案、实数二分、lower_bound前缀和多次区间求和、二维矩阵区域求和预处理O(n)查询O(1)二维前缀和、带修改的前缀和差分频繁区间加/减最后统一查询O(n)二维差分、差分前缀和组合双指针有序数组找配对、最长/最短子段、滑动窗口O(n)相向双指针、同向双指针滑动窗口字符串排序规则定制、子串查找、回文、最长公共前缀视具体技术而定字符串哈希二分、后缀数组入门下面逐个展开。我会给出模板代码但更重要的是讲清楚“为什么这么写”“哪里最容易写错”。2. 排序模板代码之外还有一个隐藏考点2.1 别急着手写快排先确认你到底需要哪种排序很多人一提到排序就条件反射地写快排但实际工程和算法题里内置排序几乎总是首选。C用std::sortJava用Arrays.sortJavaScript用Array.prototype.sortPython用sorted这些内置实现已经针对大量场景优化过了。但内置排序有个容易被忽略的细节稳定性。C的std::sort是不稳定排序std::stable_sort才是稳定的Java对基本类型数组用的是双轴快排不稳定对对象数组用的是TimSort稳定。什么时候必须用稳定排序最典型的就是多关键字排序先按分数排再按学号排如果第一轮排序不稳定第二轮会打乱第一轮相同关键字内部的相对顺序。我自己被这个问题坑过一次。某次要求“先按部门分组再按姓名排序”我先按姓名排再按部门排结果因为用了不稳定的排序同一部门内的姓名顺序全乱了。正确做法是写一个组合比较器先比部门相同再比姓名一步到位。2.2 归并排序的真正价值逆序对统计手写归并排序在算法题里的最大价值不是排序本身而是可以在排序过程中顺手统计逆序对数量。归并排序在合并两个有序子数组时如果右侧元素比左侧元素小那么左侧从当前位置到中间位置的所有元素都和这个右侧元素构成逆序对。C模板long long mergeSort(vectorint nums, int left, int right) { if (left right) return 0; int mid left (right - left) / 2; long long cnt mergeSort(nums, left, mid) mergeSort(nums, mid 1, right); vectorint tmp(right - left 1); int i left, j mid 1, k 0; while (i mid j right) { if (nums[i] nums[j]) { tmp[k] nums[i]; } else { tmp[k] nums[j]; cnt mid - i 1; // 关键左侧剩余元素都大于 nums[j] } } while (i mid) tmp[k] nums[i]; while (j right) tmp[k] nums[j]; for (int p 0; p tmp.size(); p) nums[left p] tmp[p]; return cnt; }注意cnt mid - i 1这一句它利用了“左右两个子数组已经各自有序”的性质一次性统计多个逆序对而不是逐个比较这才是归并排序统计逆序对能保持O(n log n)的关键。2.3 计数排序当数据范围很小时O(n) 完胜比较排序还有一个排序在刷题中经常被忽略——计数排序。当值的范围有限比如成绩在0到100之间或者字符最多26种可以用计数数组统计每个值出现的次数然后按顺序放回原数组。这种场景下计数排序是O(n k)的比任何基于比较的排序都快。比如说按字母的频率对字符串中的字符排序这类题直接建一个26长度的桶就行。这道题的思路后面讲字符串时还会再用到。3. 二分查找真正的难点不是“查到了”而是“查边界”3.1 一个模板吃透整数二分二分查找的写法五花八门有人用闭区间有人用左闭右开一个人一个习惯。我的建议是只记一套模板并且把“找左边界”和“找右边界”两个版本都背牢。核心思路定义check(mid)为“mid位置是否满足某种条件”然后根据条件缩小区间。C 找第一个 target 的位置即lower_boundint lower_bound(vectorint nums, int target) { int left 0, right nums.size(); // 左闭右开区间 while (left right) { int mid left (right - left) / 2; if (nums[mid] target) left mid 1; else right mid; } return left; // 第一个 target 的下标 }找第一个 target 的位置即upper_bound只要把条件改成nums[mid] target时收缩即可。这里我强调两个最容易踩的坑死循环。整数二分写成left mid; right mid且mid left (right - left) / 2时当区间长度为2可能死循环。稳妥做法是始终保持left mid 1或right mid这种必然收缩的写法不要写left mid除非你改用了mid left (right - left 1) / 2向上取整。整数溢出。不要写(left right) / 2极端情况下 left right 可能溢出 int。写left (right - left) / 2是面试官一眼就加分的小细节。3.2 二分答案把“求最值”变成“判可行”比基础二分更重要的是“二分答案”这个思想。它的适用场景很典型题目要你求“最大的最小值”“最小的最大值”而且答案本身是一个单调的数轴——如果某个值可行那么更宽松的值也可行。经典题“在D天内送达包裹的能力”就是典型。左边界是单个包裹中的最大重量右边界是所有包裹总重量然后二分这个“船的运载能力”每次用模拟判断能否在D天内运完。bool canShip(vectorint weights, int cap, int days) { int cur 0, d 1; for (int w : weights) { if (cur w cap) { d; cur 0; } cur w; if (d days) return false; } return true; } int shipWithinDays(vectorint weights, int days) { int left 0, right 0; for (int w : weights) { left max(left, w); right w; } while (left right) { int mid left (right - left) / 2; if (canShip(weights, mid, days)) right mid; else left mid 1; } return left; }这类题的特征非常明显答案是一个整数范围很大直接枚举会超时但验证某个答案是否可行只需要O(n)遍历。只要出现“最大中找最小”“最小中找最大”这类措辞第一反应就应该是二分答案。3.3 实数二分的收尾方式二分不止用于整数。求平方根、求方程的根这类实数问题也可以用二分但收尾条件有讲究。一种方法是判断right - left 1e-7这样的精度阈值另一种更稳的方法是固定迭代次数比如迭代60次因为每一步区间缩小一半60次之后精度远超1e-18足够应对几乎所有题目。提示实数二分里不要用while (left ! right)浮点数的相等判断永远是危险的。4. 前缀和与差分区间问题的“一体两面”4.1 前缀和让区间求和变成一次减法前缀和的思路一句话就能讲明白预处理一个数组pre[i]表示前 i 个元素之和之后想求区间[l, r]的和直接用pre[r] - pre[l-1]O(1)完成。很多人对pre[0] 0这个设定不太理解我用一个生活类比假设你记录每天的花费前缀和就是“到某天为止累计花了多少钱”。想算第3天到第7天花了多少只需要“到第7天的累计”减去“到第2天的累计”中间的账不用一笔笔重新算。pre[0] 0保证第1天到第r天也能套用同一公式不用特判。二维前缀和的推导稍微复杂但记住容斥原理就不怕// 预处理 for (int i 1; i m; i) for (int j 1; j n; j) pre[i][j] a[i][j] pre[i-1][j] pre[i][j-1] - pre[i-1][j-1]; // 查询子矩阵 (x1,y1) 到 (x2,y2) 的和 int sum pre[x2][y2] - pre[x1-1][y2] - pre[x2][y1-1] pre[x1-1][y1-1];这个容斥公式一定要亲手在纸上画一遍光背诵很容易在写的时候把符号搞反。4.2 差分前缀和的逆运算区间修改的利器差分数组diff[i] a[i] - a[i-1]它是前缀和的逆操作对差分数组求前缀和就能还原原数组。差分最经典的应用场景是频繁对某个区间整体加上同一个值最后才统一询问数组的最终值。比如“在数组的 [l, r] 区间上加 val”朴素做法是遍历区间逐项加复杂度O(n)用差分只需要两步diff[l] val; diff[r 1] - val;最后一次性求前缀和就能得到每个位置的最终值。整个过程对所有操作的总复杂度是O(n m)m是操作次数。我第一次接触这个技巧时觉得有点反直觉明明我是在“修改数组”怎么只改两个位置就行了后来我换了个角度理解差分记录的不是某个位置的值而是“变化量”。区间加val本质上是在l位置开始产生一个向上的变化在r1位置产生一个向下的抵消。就像在水池里制造一个“波”前缀和就是把这个波完整展开成水面高度。4.3 差分和前缀和组合使用的高级套路真正有意思的是差分和前缀和可以叠着用。二维差分可以高效处理矩形区域的整体加值更进一步的如果题目要求“支持区间加区间求和”那就要在差分之上再做一层处理或者考虑用树状数组 / 线段树。热词里提到“树状数组维护长度 n 16 的序列。查询前缀和 sum(11) 与单点修改 add(3, x)”这正是前缀和思路的延伸。线段树和树状数组本质上都在维护“可动态修改的前缀和”理解了静态前缀和的原理再去看这些高级数据结构你会觉得顺理成章。提示刷题时遇到“区间统一加值 多次查询”这类题先想清楚是“先修改后查询”用差分还是“边修改边查询”用树状数组/线段树选错数据结构是常见的失分原因。5. 双指针把双重循环降维的思维模型5.1 相向双指针有序数组的黄金搭档最经典的双指针场景是“在有序数组中找到两个数使其和等于target”。暴力做法是双重循环O(n²)双指针做法从两端往中间走O(n)解决int left 0, right nums.size() - 1; while (left right) { int sum nums[left] nums[right]; if (sum target) return {left, right}; else if (sum target) left; // 和太小左指针右移变大 else right--; // 和太大右指针左移变小 }这里每一步移动的确定性来自有序性左指针右移会让和变大右指针左移会让和变小。正是这种单调性保证了指针移动的每一步都不会错过可能的答案。三数之和、四数之和都是这个思路的扩展固定第一个数剩余部分用相向双指针扫。5.2 同向双指针滑动窗口子段问题的利器同向双指针也叫滑动窗口处理的是“最长/最短满足某条件的连续子数组”这类问题。核心模板是int left 0, ans 0; for (int right 0; right n; right) { // 加入 nums[right] 到窗口更新窗口状态 add(nums[right]); // 窗口不满足条件时移动 left 收缩窗口 while (!valid()) { remove(nums[left]); left; } // 此时窗口是一个合法窗口更新答案 ans max(ans, right - left 1); }这个模板的精髓在于right指针负责“扩展窗口”left指针负责“收缩窗口”每个元素最多进窗口一次、出窗口一次所以整体复杂度是O(n)而不是看起来的O(n²)。我个人的理解是滑动窗口本质上是“暴力枚举所有右端点的同时用单调性只保留最优的左端点”。当某个left不再满足条件时更大的left也就没有必要再尝试了这种单调性判断是使用滑动窗口的前提。5.3 双指针能用起来的三个特征不是所有题目都能用双指针。根据我的经验能用双指针的题通常有以下特征之一数组有序需要找配对关系求解对象是连续子数组/子串且有明确的合法条件要求“去重”并在一次遍历中统计信息比如链表判环的快慢指针。反过来如果数据无序、子段条件不满足单调性、或者需要统计的是全局组合数双指针大概率不适用要回到排序、哈希表或者其它方案。6. 字符串题目把前面所有技巧集合起来考的“考场”6.1 字符串排序最容易踩的自定义比较器坑字符串排序里最经典的坑来自JavaScript的sort()默认比较规则是把元素转成字符串再按字典序比较所以[1, 2, 10].sort()的结果是[1, 10, 2]而不是[1, 2, 10]。[1, 2, 10].sort((a, b) a - b); // [1, 2, 10]必须显式传入比较函数在算法题里字符串排序经常需要自定义规则。比如按“字符串长度优先、长度相同按字典序”排序C可以写sort(strs.begin(), strs.end(), [](const string a, const string b) { if (a.size() ! b.size()) return a.size() b.size(); return a b; });关键点比较器必须满足严格弱序也就是“相等时返回false”否则排序结果未定义。很多人喜欢在比较器里写return a.size() b.size()这是错的。6.2 字符串哈希 二分快速找最长公共前缀字符串题里一个非常实用的组合是“字符串哈希 二分”。先对字符串计算前缀哈希值然后二分枚举前缀长度用O(1)时间比较两个子串是否相等。这背后的原理是把字符串比较转化为整数比较前提是哈希冲突概率足够低。常见哈希写法用双哈希或取一个大质数模数降低冲突class StringHash { vectorunsigned long long h, p; public: StringHash(const string s) { int n s.size(); h.resize(n 1); p.resize(n 1); p[0] 1; const int base 131; for (int i 1; i n; i) { h[i] h[i-1] * base s[i-1]; p[i] p[i-1] * base; } } // 获取 [l, r] 区间子串的哈希值下标从1开始 unsigned long long get(int l, int r) { return h[r] - h[l-1] * p[r - l 1]; } };base取131或13331是竞赛圈的常见习惯unsigned long long 自然溢出相当于对2^64取模实际使用中冲突概率很低。有了这个结构求两个字符串的最长公共前缀就可以二分int l 0, r min(s1.size(), s2.size()); while (l r) { int mid (l r 1) / 2; if (hash1.get(1, mid) hash2.get(1, mid)) l mid; else r mid - 1; } // l 就是最长公共前缀长度这道题本身没多大难度但它把“字符串”“哈希”“二分”三个知识点从头到尾串了一遍非常值得亲手写一遍。6.3 用双指针处理字符串子段问题字符串的双指针题往往和“子串”“回文”“窗口”有关。比如“无重复字符的最长回文子串”需要动态维护窗口内字符是否重复用unordered_set或计数数组配合滑动窗口模板即可。回文相关的经典双指针题是“验证回文串”和“最长回文子串”。前者用相向双指针从两头往中间走遇到非字母数字字符跳过后者需要中心扩展法本质上也是双指针——每个奇/偶中心向左右同时扩展。注意字符串题里“字符集大小”常被忽略。如果只包含26个小写字母用int cnt[26]就够如果包含Unicode字符就要用哈希表。面试中先问清楚字符集范围这是一个非常加分的习惯。7. 刷题与总结的个人建议7.1 给每个技巧建立“触发词”清单我在前面反复强调“看到什么信号用哪个技巧”这不是套话。你可以像我一样给每个技巧整理一组触发词看到“逆序对”“稳定排序”“按规则排列” → 排序看到“有序”“最大值最小化”“最小值最大化” → 二分看到“多次区间求和”“矩阵区域和” → 前缀和看到“区间统一加值”“最后统一查询” → 差分看到“两数之和”“最长子串”“连续子数组” → 双指针。整理触发词能帮你在看到题目时快速缩小思考范围而不是漫无目的地尝试。7.2 亲手推一遍的时间投资永远值得无论是二分的区间收缩、二维前缀和的容斥公式还是滑动窗口的单调性证明我的建议都是在纸上画一个小的测试用例手动模拟几轮。我见过太多人收藏了一堆模板结果一上机就卡在符号和边界上。手推一遍之后这些细节会变成肌肉记忆。另外你可以给自己限定时间重写这些模板5分钟内写不出归并排序的逆序对统计说明还没真正掌握。基本功的评判标准不是“看过”而是“随手能写”。7.3 后续可以怎么扩展这篇文章是基础技巧的第一部分。后面的路线比较自然排序学会了可以接触堆排序、快速选择第K大问题二分学会了可以看三分、二分图判定前缀和和差分学会了可以升级到树状数组、线段树双指针学会了可以接触单调栈、单调队列字符串这块则可以延伸到KMP、Trie树、AC自动机。一次把高级算法全铺开反而容易消化不良先把这五样磨透后面的路会平坦得多。我自己后来回头看面试中90%的算法题最终都归约到这些基础技巧的变体——把地基打牢才是性价比最高的投入。