算法实战：前缀和技巧解中心下标与数组乘积问题
27. 寻找数组的中心下标
题目描述
给定一个整数数组 nums，请编写一个算法返回该数组的「中心下标」。
数组的「中心下标」是指数组中满足以下条件的索引：
- 该索引左侧所有元素之和等于右侧所有元素之和。
- 如果不存在这样的索引，返回
-1。
解题思路
这道题的核心在于找到数组中一个索引，使得该索引左侧所有元素之和等于右侧所有元素之和。
直观的想法是遍历每个位置，分别计算左右两边的和，但这样会导致 O(N²) 的时间复杂度。为了优化到 O(N)，我们可以利用前缀和的思想。
核心逻辑：
- 预处理出两个数组：
f[i]：表示索引i左侧所有元素的和（前缀和）。g[i]：表示索引i右侧所有元素的和（后缀和）。
- 遍历数组，判断
f[j] == g[j]是否成立。 - 若相等，则
j即为中心下标；若遍历结束未找到，返回-1。
注意：对于边界情况，最左侧元素的左侧和为 0，最右侧元素的右侧和也为 0。
C++ 代码实现
class Solution {
public:
int pivotIndex(vector<int>& nums) {
int n = nums.size();
vector<int> f(n), g(n);
// f[0] 默认为 0，无需显式赋值
for (int i = 1; i < n; i++) {
f[i] = f[i - 1] + nums[i - 1];
}
// g[n-1] 默认为 0，无需显式赋值
for (int i = n - 2; i >= 0; i--) {
g[i] = g[i + 1] + nums[i + 1];
}
for (int j = 0; j < n; j++) {
if (f[j] == g[j]) {
return j;
}
}
return -1;
}
};
28. 除自身以外数组的乘积
题目描述
给你一个整数数组 nums，请你返回一个数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
约束条件：
- 不能使用除法。
- 时间复杂度需控制在 O(N)。
解题思路
既然不能用除法，且要求线性时间复杂度，暴力枚举显然不可行。我们需要观察结果的结构。
对于任意位置 i，最终结果 ret[i] 由两部分组成：
i左侧所有元素的乘积：nums[0] * ... * nums[i-1]i右侧所有元素的乘积：nums[i+1] * ... * nums[n-1]
这本质上就是前缀积和后缀积的结合。我们可以利用两个辅助数组来存储这些信息：
post[i]：记录i位置之前（左侧）所有元素的前缀乘积。suf[i]：记录i位置之后（右侧）所有元素的后缀乘积。
最后将对应位置的乘积相乘即可得到结果。
C++ 代码实现
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
vector<int> f(n), g(n), ret(n);
// 初始化边界值，乘法单位元为 1
f[0] = 1;
g[n - 1] = 1;
// 计算左侧前缀乘积
for (int i = 1; i < n; i++) {
f[i] = f[i - 1] * nums[i - 1];
}
// 计算右侧后缀乘积
for (int j = n - 2; j >= 0; j--) {
g[j] = g[j + 1] * nums[j + 1];
}
// 合并结果
for (int i = 0; i < n; i++) {
ret[i] = f[i] * g[i];
}
return ret;
}
};
总结
这两个问题都展示了前缀和（或前缀积）思想在数组处理中的强大之处。
- 空间换时间：通过预处理构建辅助数组，将原本需要重复计算的子问题结果缓存起来，从而将时间复杂度从 O(N²) 降低到 O(N)。
- 边界处理：在处理首尾元素时，要注意初始值的设定（求和为 0，求积为 1），这是容易出错的地方。
- 扩展性：这种模式不仅适用于求和与乘积，还可以推广到其他可结合运算的场景中。
