寻找数组的中心索引

发表于 更新于 分类于 阅读次数： 本文字数： 557 阅读时长 ≈ 2 分钟

自己想到的解法，就是循环遍历数组中的每一个元素，求出左侧数之和和右侧数之和，然后判断是否相等。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
var pivotIndex = function (nums) {
  for (let i = 0; i < nums.length; i++) {
    let sumLeft = 0;
    let sumRight = 0;

    // 1.求左侧数之和
    for (let l = 0; l < i; l++) {
      sumLeft += nums[l];
    }

    // 2.求右侧数之和
    for (let r = i + 1; r < nums.length; r++) {
      sumRight += nums[r];
    }

    // 判断
    if (sumLeft === sumRight) {
      return i;
    } else if (i === nums.length - 1) {
      return -1;
    } else {
      continue;
    }
  }
};
nums = [1, 7, 3, 6, 5, 6];
console.log(pivotIndex(nums));

由于使用了嵌套的 for 循环，所以时间复杂度为 O(n²)。

结合力扣官方解法和 gpt 给出的答案，不得不说， gpt 真是辅助开发的好伙伴啊！！！又发现了它的一个妙用 O(∩_∩)O~~

可以使用前缀和（Prefix Sum）来优化这段代码，从而将时间复杂度降低到 O(n)。前缀和是一种常用的技巧，它可以在一次遍历数组的过程中，将某个位置的元素之前所有元素的累加和计算出来，从而避免了重复计算。

当中心索引左侧或右侧没有元素时，即为零个项相加，这在数学上称作「空和」（empty sum）。在程序设计中我们约定「空和是零」。

优化方案的思路是先计算出数组的总和 totalSum，然后遍历数组一次，在遍历的过程中，用变量 leftSum 记录当前索引之前的所有元素的累加和。在每次遍历时，检查 leftSum 是否等于 totalSum - leftSum - nums[i]，如果是，则说明找到了中心索引，直接返回当前索引 i。

这种优化方案的时间复杂度为 O(n)，只需要一次遍历数组即可找到中心索引，而不需要嵌套循环。同时，空间复杂度仍然为 O(1)，因为只使用了常数个额外的变量来保存结果。这样的优化方案在处理大规模数组时性能会更好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function findCenterIndex(nums) {
  const totalSum = nums.reduce((acc, num) => acc + num, 0);
  let leftSum = 0;

  for (let i = 0; i < nums.length; i++) {
    if (leftSum === totalSum - leftSum - nums[i]) {
      return i;
    }
    leftSum += nums[i];
  }

  return -1;
}

const nums = [1, 7, 3, 6, 5, 6];
const centerIndex = findCenterIndex(nums);
console.log(centerIndex); // 输出: 3