寻找数组的中心下标

力扣题库-724

问题描述

给定一个整数类型的数组nums，请编写一个能够返回数组“中心索引”的方法。 我们是这样定义数组中心索引的：数组中心索引的左侧所有元素相加的和等于右侧所有元素相加的和。 如果数组不存在中心索引，那么我们应该返回 -1。如果数组有多个中心索引，那么我们应该返回最靠近左边的那一个。

示例 1:
输入：nums = [1, 7, 3, 6, 5, 6]
输出：3
解释：
中心下标是 3 。
左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ，
右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，二者相等。

示例 2:
输入：nums = [1, 2, 3]
输出：-1
解释：
数组中不存在满足此条件的中心下标。

function findPivotIndex($nums = []) {
    $count = count($nums);
    if ($count == 1) {
        return -1;
    }
    $total   = array_sum($nums);
    $leftSum = 0; // 左边之和
    for ($i = 0; $i < $count; $i++) {
        // ($total - $nums[$i] - $leftSum) 当前索引的右边之和
        if ($leftSum == ($total - $nums[$i] - $leftSum)) {
            return $i;
        } else {
            $leftSum += $nums[$i];
        }
    }
    return -1;
}

递归方式实现

function findPivotIndex2($index = 0, $nums = []) {
    $count = count($nums);
    // 元素少于一个或者未找到中心索引返回-1
    if ($count == 1 || $index >= $count) {
        return -1;
    }
    $leftSum = $rightSum = 0;
    // 假设：第一个中心索引为0
    // 计算左边之和（0->$index）
    for ($i = 0; $i < $index; $i++) {
        $leftSum += $nums[$i];
    }
    // 右边之和（$index + 1 ->$count）
    for ($j = $index + 1; $j < $count; $j++) {
        $rightSum += $nums[$j];
    }
    if ($leftSum === $rightSum) {
        return $index;
    } else {
        // 注意：条件不成立时，一定要 return 递归函数，不然无法正常返回。
        return findPivotIndex2($index + 1, $nums);
    }
}