常见算法技巧：双指针、滑动窗口、前缀和、差分数组、位运算技巧
各位同学好，我是老林。今天咱们聊聊嵌入式开发里最常用的几个算法技巧。说实话，我写了十几年C代码，这些技巧几乎每天都在用。你想想看，不管是做传感器数据处理，还是搞通信协议解析，这些方法都能帮你写出更高效的代码。
我个人习惯把这类技巧叫做「编程的瑞士军刀」——小巧、实用、关键时刻能救命。咱们一个一个来看。
一、双指针技巧
双指针，说白了就是用两个指针来遍历数据结构。听起来简单，但用好了威力很大。
我在项目中遇到过这样一个场景：需要从一个有序数组中找出两个数，使它们的和等于目标值。用暴力法要O(n²)，但双指针只需要O(n)。
核心思想：一个指针从头走，一个指针从尾走，根据条件调整移动方向。
// 两数之和 - 双指针法
int* twoSum(int* nums, int numsSize, int target) {
int left = 0, right = numsSize - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
// 找到了！
int* result = malloc(2 * sizeof(int));
result[0] = left;
result[1] = right;
return result;
} else if (sum < target) {
left++; // 和太小，左指针右移
} else {
right--; // 和太大，右指针左移
}
}
return NULL;
}我的经验：双指针最怕的是边界条件。我曾经因为没处理好 left == right 的情况，导致数组越界，查了整整一下午。记住：循环条件用 left < right，别用 left <= right。
双指针还有几个变种：
- 快慢指针：一个走得快，一个走得慢。常用于链表判环、找中点。
- 左右指针：上面例子就是。常用于有序数组、字符串反转。
- 滑动窗口：这个咱们下面单独讲。
二、滑动窗口
滑动窗口其实是双指针的一种特殊形式。两个指针维护一个「窗口」，窗口在数据上滑动，每次只更新窗口边界的变化。
嗯，这里要注意：滑动窗口特别适合处理「连续子数组/子串」的问题。
// 长度最小的子数组 - 滑动窗口
int minSubArrayLen(int target, int* nums, int numsSize) {
int left = 0, right = 0;
int sum = 0, minLen = INT_MAX;
while (right < numsSize) {
sum += nums[right]; // 右边界扩展
right++;
while (sum >= target) {
// 更新最小长度
int curLen = right - left;
if (curLen < minLen) minLen = curLen;
sum -= nums[left]; // 左边界收缩
left++;
}
}
return minLen == INT_MAX ? 0 : minLen;
}我曾经踩过的坑：滑动窗口的左右边界更新顺序一定要搞清楚。是先移动再计算，还是先计算再移动？我建议你画个图，把每一步的指针位置标出来，这样不容易出错。
滑动窗口的典型应用场景：
- 字符串中找无重复字符的最长子串
- 数组中找满足条件的最短/最长子数组
- 数据流中的平均值计算
三、前缀和
前缀和是个很巧妙的思想。它把「区间和」的问题，转化成了「两个前缀和的差」。
说白了就是：先算好从开头到每个位置的累加和，存起来。以后要算任意区间的和，直接拿两个前缀和一减就完事了。
// 构建前缀和数组
int* buildPrefixSum(int* nums, int n) {
int* prefix = malloc((n + 1) * sizeof(int));
prefix[0] = 0; // 哨兵，方便计算
for (int i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}
return prefix;
}
// 查询区间 [l, r] 的和
int rangeSum(int* prefix, int l, int r) {
return prefix[r + 1] - prefix[l];
}我的习惯：前缀和数组长度设为 n+1，第0个位置放0。这样处理边界时不用单独判断，代码更干净。我在做嵌入式数据采集时，经常用这个技巧来快速计算传感器数据的滑动平均值。
前缀和的优势：
- 预处理O(n)，查询O(1)
- 空间换时间，典型思路
- 可以扩展到二维（二维前缀和）
四、差分数组
差分数组是前缀和的「逆运算」。前缀和用来快速求区间和，差分数组用来快速做区间加减。
你想想看：如果要对一个数组的某个区间频繁做加减操作，每次都遍历区间，效率太低了。差分数组就是来解决这个问题的。
// 差分数组实现区间加减
void rangeAdd(int* diff, int l, int r, int val) {
diff[l] += val;
if (r + 1 < n) diff[r + 1] -= val;
}
// 从差分数组还原原数组
void buildFromDiff(int* diff, int* nums, int n) {
nums[0] = diff[0];
for (int i = 1; i < n; i++) {
nums[i] = nums[i - 1] + diff[i];
}
}核心理解：差分数组只记录变化量。对区间[l, r]加val，只需要在diff[l]加val，在diff[r+1]减val。最后累加一次就能得到结果。
我在项目中用过这个技巧：当时需要控制LED灯的亮度渐变，每个LED的亮度变化区间不同。用差分数组，一次就能算出所有LED的最终亮度，比逐一遍历快了一个数量级。
五、位运算技巧
位运算，是嵌入式工程师的必修课。直接操作寄存器、设置标志位、快速计算，都离不开它。
我个人觉得，位运算是最能体现C语言「贴近硬件」这个特点的地方。
// 常用位运算操作
// 判断奇偶
if (x & 1) // 奇数
else // 偶数
// 交换两个数（不用临时变量）
a ^= b; b ^= a; a ^= b;
// 取最低位的1
int lowbit = x & (-x);
// 清除最低位的1
x = x & (x - 1);
// 判断是否是2的幂
bool isPowerOfTwo = (x > 0) && ((x & (x - 1)) == 0);注意：位运算虽然快，但可读性差。我建议在关键性能路径上用位运算，普通逻辑还是用常规写法。我曾经接手过一个项目，前任把所有判断都用位运算写，结果维护起来简直噩梦。
位运算的常见应用：
- 状态标志管理（用不同bit表示不同状态）
- 权限控制（读、写、执行权限用三位表示）
- 快速乘除2的幂（左移/右移）
- 哈希函数中的散列计算
知识体系总览
下面这张图，我把这五种技巧的关系和适用场景整理了一下。你可以把它当作一个快速参考。
总结一下
这五种技巧，说白了都是「空间换时间」的思路。预处理一些信息，然后快速回答查询。在嵌入式开发中，内存往往有限，所以用的时候要权衡一下。
我个人建议：
- 数据量小的时候，暴力法最可靠，别为了炫技用复杂技巧
- 数据量大、查询频繁的时候，优先考虑这些技巧
- 写代码时先保证正确，再考虑优化
好了，这一章就到这里。这些技巧你多用几次，就会形成肌肉记忆。下次遇到问题，脑子里自然就会想：「能不能用双指针？能不能用前缀和？」
最后说一句：算法技巧是死的，但问题是活的。多练习、多总结，你也能写出优雅高效的C代码。