物流公司网站建设系统规划_武汉最新新闻_优化公司网站_洛阳seo网络推广

1. 题目链接

LeetCode 724. 寻找数组的中心下标

---

2. 题目描述

• 输入：一个整数数组 nums。
• 目标：找到数组的中心下标，即满足左侧所有元素和等于右侧所有元素和的位置（左侧/右侧可以为空，和为 0）。
• 输出：返回最左侧的中心下标；若不存在，返回 -1。

---

3. 示例分析

示例 1：
输入：nums = [1, 7, 3, 6, 5, 6]
输出：3
解释： 中心下标为 3，左侧和 1+7+3=11，右侧和 5+6=11。

示例 2：
输入：nums = [2, 1, -1]
输出：0
解释： 中心下标为 0，左侧和为空（0），右侧和 1+(-1)=0。

---

4. 算法思路

前缀和算法

1. 预处理阶段：

   • 构建两个数组 f 和 g：
     • f[i] 表示前 i 个元素（即 nums[0] 到 nums[i-1]）的和。
     • g[i] 表示后 n-i-1 个元素（即 nums[i+1] 到 nums[n-1]）的和。
   • 递推公式：

     f[i] = f[i-1] + nums[i-1]  // 从左到右累加  
     g[i] = g[i+1] + nums[i+1]  // 从右到左累加  
     

   • 时间复杂度：O(n)。

2. 比较阶段：

   • 遍历每个下标 i，若 f[i] == g[i]，则 i 是中心下标。
   • 时间复杂度：O(n)。

暴力枚举法

• 对于每个下标 i，直接遍历计算左侧和与右侧和：

  int left = 0, right = 0;  
  for (int j = 0; j < i; j++) left += nums[j];  
  for (int j = i+1; j < n; j++) right += nums[j];  
  if (left == right) return i;  
  

• 时间复杂度：O(n²)。

---

5. 边界条件与注意事项

1. 空数组：若数组为空，直接返回 -1。

2. 单元素数组：若 n=1，左侧和右侧均为 0，返回 0。

3. 数值溢出：使用 long long 存储前缀和，避免 int 溢出。

4. 索引范围：预处理时注意数组的起始和终止索引（如 g 数组从 n-2 开始反向计算）。

---

6. 代码实现

class Solution {
public:int pivotIndex(vector<int>& nums) {int n = nums.size();if (n == 0) return -1;vector<long long> f(n, 0), g(n, 0);// 预处理前缀和 f[i] = sum(nums[0..i-1])for (int i = 1; i < n; i++)  f[i] = f[i - 1] + nums[i - 1];// 预处理后缀和 g[i] = sum(nums[i+1..n-1])for (int i = n - 2; i >= 0; i--)  g[i] = g[i + 1] + nums[i + 1];// 比较for (int i = 0; i < n; i++) if (f[i] == g[i]) return i;return -1;}
};

---

7. 对比图表：前缀和 vs 暴力枚举

对比维度	前缀和算法	暴力枚举法
时间复杂度	O(n)	O(n²)
空间复杂度	O(n)	O(1)
适用场景	单次查询即可解决问题	仅适用于小规模数据
代码复杂度	需预处理，逻辑清晰	直接遍历，代码简单但低效
数值溢出风险	使用 long long 避免溢出	多次累加可能溢出
边界处理	自动处理空数组和单元素情况	需手动处理边界

---

8. 总结

• 前缀和算法通过 O(n) 预处理，将单次查询优化到 O(1)，是解决此类问题的标准方法。
• 暴力枚举法虽然空间占用低，但时间复杂度高，仅适用于极小数据规模。
• 在工程实践中，优先选择前缀和算法以应对可能的输入规模变化。