LeetCode 724, 1991 —— 寻找数组中心下标

题目链接

• https://leetcode-cn.com/problems/find-pivot-index/
• https://leetcode-cn.com/problems/find-the-middle-index-in-array/

题目描述

给你一个下标从 0 开始的整数数组 nums，请你找到 最左边 的中间位置 middleIndex（也就是所有可能中间位置下标最小的一个）。

中间位置 middleIndex 的数组下标满足：

$nums[0]$ $+$ $nums[1]$ $+$ $…$ $+$ $nums[middleIndex - 1]$ $===$ $nums[middleIndex + 1]$ $+$ $nums[middleIndex + 2]$ $+$ $…$ $+$ $nums[nums.length - 1]$

如果 middleIndex === 0，左边部分的和定义为 0，如果 middleIndex === nums.length - 1 ，右边部分的和定义为 0。

请你返回满足上述条件 最左边 的 middleIndex，如果不存在这样的中间位置，请你返回 -1。

示例

示例 1：

输入： nums = [2, 3, -1, 8, 4]
输出： 3
解释：
下标 3 之前的数字和为：2 + 3 + -1 = 4
下标 3 之后的数字和为：4 = 4

示例 2：

输入： nums = [1, -1, 4]
输出： 2
解释：
下标 2 之前的数字和为：1 + -1 = 0
下标 2 之后的数字和为：0

示例 3：

输入： nums = [2, 5]
输出： -1
解释：
不存在符合要求的 middleIndex。

示例 4：

输入： nums = [1]
输出： 0
解释：
下标 0 之前的数字和为：0
下标 0 之后的数字和为：0

题解

暴力破解

暴力破解就是一边遍历一边通过累加求左侧的和，此时右侧的和未知，再嵌套循环求右侧的总和，如果左右和相等则结束循环直接返回索引，全部遍历完没有找到 middleIndex 则返回 -1。

const findMiddleIndex = (nums) => {
  let leftSum = 0;

  for (let i = 0; i < nums.length; i++) {
    let rightSum = 0;

    for (let j = i + 1; j < nums.length; j++) {
      rightSum += nums[j];
    }

    if (leftSum === rightSum) {
      return i;
    }

    leftSum += nums[i];
  }

  return -1;
}

复杂度分析：

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(1)$

前缀和

在暴力破解时，之所以会在每一次循环中再次嵌套循环是因为右侧的和未知，如果已知总和为 sum，遍历到当前项的值为 num，遍历累加求出的左侧总和为 leftSum，则可以求出右侧总和 rightSum 得：

$rightSum = sum - leftSum - num$

若 leftSum 与 rightSum 相等，则：

由：$leftSum = sum - leftSum - num$
推出：$2 * leftSum + num = sum$

所以先求出 sum，就可以在遍历过程中通过公式计算的结果判断是否左侧和右侧的总和相等。

const findMiddleIndex = (nums) => {
  const sum = nums.reduce((sum, cur) => sum + cur, 0);
  let leftSum = 0;

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

    leftSum += nums[i];
  }

  return -1;
}

复杂度分析：

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$