在算法竞赛中通过巧妙的技巧将时间复杂度从暴力解法的 O(n²)、O(n³) 甚至 O(n⁴) 优化到 O(n log n) 或 O(n) 是取胜的关键。这些技巧的核心在于避免不必要的计算、利用数据特性、转换问题视角以及应用高效的数据结构。以下结合具体场景和代码系统梳理这些优化技巧。一、利用排序与双指针消除多重循环这是将多项式时间复杂度优化到线性或对数线性的经典手段尤其适用于“多个元素组合求和/比较”类问题。典型问题在一个数组中找出所有不重复的三元组[a, b, c]使得a b c 0三数之和。暴力解法三重循环枚举所有组合时间复杂度O(n³)。优化技巧固定一个数将三数之和问题转化为两数之和问题再对剩余部分使用排序 双指针。先对数组排序O(n log n)。遍历数组固定第一个数nums[i]。对于nums[i1...n-1]部分使用头尾双指针left和right向中间逼近寻找nums[left] nums[right] -nums[i]。根据当前和与目标值的大小关系移动指针。由于数组有序移动方向是确定的。vectorvectorint threeSum(vectorint nums) { vectorvectorint res; int n nums.size(); sort(nums.begin(), nums.end()); // 关键先排序 for (int i 0; i n - 2; i) { if (i 0 nums[i] nums[i-1]) continue; // 跳过重复的固定数 int target -nums[i]; int left i 1, right n - 1; while (left right) { // 双指针扫描 int sum nums[left] nums[right]; if (sum target) { res.push_back({nums[i], nums[left], nums[right]}); // 跳过重复的左指针和右指针元素 while (left right nums[left] nums[left1]) left; while (left right nums[right] nums[right-1]) right--; left; right--; } else if (sum target) { left; } else { right--; } } } return res; }复杂度分析排序 O(n log n)外层循环 O(n)内层双指针总计 O(n)整体O(n log n) O(n²) O(n²)。相比于 O(n³) 是质的飞跃 。扩展应用此技巧同样适用于“最接近的三数之和”、“四数之和”等问题通过增加一层循环并内嵌双指针来解决。二、哈希表unordered_map/set以空间换时间哈希表能在平均 O(1)时间内完成查找和插入是优化“查找特定元素”或“记录状态”问题的利器。典型问题给定一个整数数组和一个目标值找出数组中和为目标值的两个数的下标两数之和。暴力解法双重循环时间复杂度O(n²)。优化技巧一次遍历使用哈希表记录每个元素的值及其索引。对于当前元素nums[i]计算complement target - nums[i]然后检查complement是否在哈希表中。vectorint twoSum(vectorint nums, int target) { unordered_mapint, int numMap; // key: 数值, value: 索引 for (int i 0; i nums.size(); i) { int complement target - nums[i]; if (numMap.find(complement) ! numMap.end()) { return {numMap[complement], i}; } numMap[nums[i]] i; // 先查后存避免自己匹配自己 } return {}; }复杂度分析单次遍历 O(n)每次哈希查找/插入平均 O(1)整体O(n)。扩展应用哈希表广泛用于子数组和问题配合前缀和、判断重复、**缓存中间结果记忆化**等场景。三、前缀和与差分数组优化区间操作当需要频繁查询数组某个区间的和或者对某个区间进行统一增减操作时前缀和与差分是标准优化工具。前缀和 (Prefix Sum)用于快速计算任意区间和。预处理prefix[i] nums[0] nums[1] ... nums[i]。查询区间[l, r]的和sum prefix[r] - (l 0 ? prefix[l-1] : 0)。将单次区间和查询从 O(n) 优化到O(1)。差分数组 (Difference Array)用于快速对区间进行增减操作。定义diff[i] nums[i] - nums[i-1](i≥1)diff[0] nums[0]。要对区间[l, r]的所有元素加val只需执行diff[l] val; if (r 1 n) diff[r1] - val;操作完成后通过差分数组的前缀和即可还原新的nums数组。将多次区间修改每次 O(n)的复杂度优化为每次修改O(1)最后一次性 O(n) 重建。// 差分数组应用示例航班预订统计 vectorint corpFlightBookings(vectorvectorint bookings, int n) { vectorint diff(n 1, 0); // 多开一位方便处理 r1 for (auto b : bookings) { int l b[0] - 1, r b[1] - 1, val b[2]; diff[l] val; diff[r 1] - val; // 注意边界 } vectorint answer(n); answer[0] diff[0]; for (int i 1; i n; i) { answer[i] answer[i-1] diff[i]; // 前缀和还原数组 } return answer; }四、二分查找优化“最大值最小化”或“可行性判定”当问题可以转化为“对于某个猜测的答案 X判断是否可行”并且可行性判断函数f(X)是单调的即 X 越大越容易满足或越难满足就可以用二分法在答案范围内搜索最优解。典型问题给定一个非负整数数组nums和一个整数m你需要将这个数组分成m个连续的非空子数组使得这m个子数组各自和的最大值最小。暴力解法枚举所有分割方式不可行。优化技巧二分搜索这个“最小的最大值”。搜索范围[max(nums), sum(nums)]。判定函数canSplit(limit)贪心地分割数组使得每个子数组的和尽可能接近但不超过limit统计需要的子数组数量是否 ≤ m。如果canSplit(mid)为真说明答案可能更小搜索左半部分否则搜索右半部分。int splitArray(vectorint nums, int m) { long long left *max_element(nums.begin(), nums.end()); long long right accumulate(nums.begin(), nums.end(), 0LL); while (left right) { long long mid left (right - left) / 2; if (canSplit(nums, m, mid)) { right mid; } else { left mid 1; } } return left; } bool canSplit(vectorint nums, int m, long long limit) { long long sum 0; int count 1; // 初始至少有一个子数组 for (int num : nums) { if (sum num limit) { count; sum num; if (count m) return false; } else { sum num; } } return true; }复杂度分析二分搜索 O(log S)其中 S 是总和与最大值的差。每次判定需要 O(n)。总复杂度O(n log S)远优于暴力枚举。五、单调栈/队列维护局部最优解用于解决“寻找每个元素左边/右边第一个比它大/小的元素”、“滑动窗口最大值”等问题。单调栈通常维护一个栈内元素单调递增或递减的栈。// 示例每日温度 - 找下一个更高温度的天数 vectorint dailyTemperatures(vectorint temps) { int n temps.size(); vectorint ans(n, 0); stackint stk; // 栈中存储下标温度值从栈底到栈顶递减 for (int i 0; i n; i) { while (!stk.empty() temps[i] temps[stk.top()]) { int idx stk.top(); stk.pop(); ans[idx] i - idx; } stk.push(i); } return ans; }每个元素最多入栈、出栈一次时间复杂度O(n)。单调队列常用于滑动窗口问题。// 滑动窗口最大值 vectorint maxSlidingWindow(vectorint nums, int k) { dequeint dq; // 存储下标对应值从队首到队尾递减 vectorint res; for (int i 0; i nums.size(); i) { // 移除超出窗口范围的元素 if (!dq.empty() dq.front() i - k) dq.pop_front(); // 维护队列单调递减 while (!dq.empty() nums[dq.back()] nums[i]) dq.pop_back(); dq.push_back(i); if (i k - 1) res.push_back(nums[dq.front()]); } return res; }同样每个元素最多入队、出队一次时间复杂度O(n)。六、动态规划的状态设计与优化DP 优化的核心在于减少状态维度或优化状态转移。状态压缩当状态维度中的某些维度取值范围很小如只有 0/1可以用位运算压缩。示例旅行商问题TSPdp[mask][i]表示访问过城市集合mask二进制位表示且最后位于城市i的最短路径。将城市集合从数组表示压缩为一个整数。斜率优化 / 四边形不等式对于形如dp[i] min{ dp[j] cost(j1, i) }的转移方程当cost函数满足某些单调性时可以用单调队列维护候选转移集合将转移复杂度从 O(n) 降为 O(1)。属于高级技巧利用数据结构优化转移当状态转移需要查询某个区间的最值或和时可以用线段树、树状数组等将转移复杂度从 O(n) 降为 O(log n)。示例最长递增子序列 (LIS) 的 O(n log n) 解法本质是利用数组维护长度为 i 的 LIS 的最小末尾值并使用二分查找进行更新这可以看作一种特殊的数据结构优化 。七、问题转化与数学特性挖掘有时直接求解困难但转化后问题变得简单。示例1Sumsets问题UVA 10125在集合中找出最大的 d使得存在 a, b, c 满足 a b c d 且 a, b, c, d 互不相同。暴力枚举 a, b, c, d 需要 O(n⁴)。技巧性转化将等式变形为a b d - c。枚举所有 (ab) 的和及其对应的 (a,b) 对需记录最大/最小元素以保证互异存储在哈希表中。再枚举 d 和 c在哈希表中查找d - c。复杂度优化至约O(n² log n)。示例2寻找数组中的重复数或缺失数。可以利用下标与值的映射关系、异或运算的性质、或将元素值视为下标进行标记等技巧在 O(n) 时间、O(1) 额外空间内解决 。总结技巧选择指南问题特征可能适用的优化技巧目标复杂度涉及多个元素的组合、求和、比较排序 双指针O(n²) - O(n log n) 或 O(n)频繁查找特定值是否存在哈希表 (unordered_set/map)O(n) - 平均 O(1)频繁查询区间和前缀和O(n) - O(1)频繁进行区间增减操作差分数组O(n) - O(1)单次操作“最大的最小值”或可行性判定二分查找指数级 - O(n log Range)找左右第一个更大/更小元素单调栈O(n²) - O(n)滑动窗口最值问题单调队列O(nk) - O(n)状态转移依赖区间查询线段树/树状数组O(n) - O(log n)单次转移状态维度小但数量多状态压缩位运算降低空间可能简化转移公式可变形、有特殊数学性质问题转化、利用数学特性大幅降低复杂度掌握这些技巧的关键在于大量练习和举一反三。在解题时先分析暴力解法的瓶颈再思考上述哪种技巧可以突破该瓶颈是提高竞赛水平的核心路径 。参考来源UVA 10125 Sumsets 技巧性的枚举算法细节系列27时间复杂度为何还能优化python冒泡排序算法时间复杂度为nlogn_〔算法〕排序的最低时间复杂度为什么是Onlogn...几道技巧性的数组题【回溯】P8933 [JRKSJ R7] 技巧性的块速递推|普及优化C程序编译效率的一些方法