3862. 找出最小平衡下标

题目描述

给你一个整数数组 nums。

如果某个下标 i 满足以下条件，则称其为 平衡下标： i 左侧所有元素的总和等于 i 右侧所有元素的乘积。

如果左侧没有元素，则总和视为 0。同样，如果右侧没有元素，则乘积视为 1。

要求返回最小的 平衡下标，如果不存在平衡下标，则返回 -1。

示例 1：

输入： nums = [2,1,2]

输出： 1

解释：

对于下标 i = 1：

左侧总和 = nums[0] = 2
右侧乘积 = nums[2] = 2
由于左侧总和等于右侧乘积，下标 1 是平衡下标。

没有更小的下标满足条件，因此答案是 1。

示例 2：

输入： nums = [2,8,2,2,5]

输出： 2

解释：

对于下标 i = 2：

左侧总和 = 2 + 8 = 10
右侧乘积 = 2 * 5 = 10
由于左侧总和等于右侧乘积，下标 2 是平衡下标。

没有更小的下标满足条件，因此答案是 2。

示例 3：

输入： nums = [1]

输出： -1

对于下标 i = 0：

左侧为空，因此左侧总和为 0。
右侧为空，因此右侧乘积为 1。
由于左侧总和不等于右侧乘积，下标 0 不是平衡下标。

因此，不存在平衡下标，答案是 -1。

提示：

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹

解法

方法一：枚举

我们先计算出数组中所有元素的总和 \(s\)，然后，我们从右向左枚举每个下标 \(i\)，在枚举过程中，我们维护一个变量 \(p\) 来记录下标 \(i\) 右侧所有元素的乘积。当枚举到下标 \(i\) 时，我们先将 \(s\) 减去 \(nums[i]\)，然后判断 \(s\) 是否等于 \(p\)，如果相等，则返回下标 \(i\)。最后，我们将 \(p\) 乘以 \(nums[i]\)，如果 \(p\) 大于或等于 \(s\)，则说明后续的乘积只会越来越大，不可能再找到平衡下标了，因此我们可以提前结束枚举。

枚举结束后，如果没有找到平衡下标，则返回 -1。

时间复杂度 \(O(n)\)，其中 \(n\) 是数组 \(nums\) 的长度。空间复杂度 \(O(1)\)。

Python3JavaC++GoTypeScript

class Solution:
    def smallestBalancedIndex(self, nums: list[int]) -> int:
        s = sum(nums)
        p = 1
        for i in range(len(nums) - 1, -1, -1):
            s -= nums[i]
            if s == p:
                return i
            p *= nums[i]
            if p >= s:
                break
        return -1

class Solution {
    public int smallestBalancedIndex(int[] nums) {
        long s = 0, p = 1;
        for (int x : nums) {
            s += x;
        }
        for (int i = nums.length - 1; i >= 0; --i) {
            s -= nums[i];
            if (s == p) {
                return i;
            }
            p *= nums[i];
            if (p >= s) {
                break;
            }
        }
        return -1;
    }
}

class Solution {
public:
    int smallestBalancedIndex(vector<int>& nums) {
        long long s = 0, p = 1;
        for (int x : nums) {
            s += x;
        }
        for (int i = nums.size() - 1; i >= 0; --i) {
            s -= nums[i];
            if (s == p) {
                return i;
            }
            p *= nums[i];
            if (p >= s) {
                break;
            }
        }
        return -1;
    }
};

func smallestBalancedIndex(nums []int) int {
    s, p := 0, 1
    for _, x := range nums {
        s += x
    }
    for i := len(nums) - 1; i >= 0; i-- {
        s -= nums[i]
        if s == p {
            return i
        }
        p *= nums[i]
        if p >= s {
            break
        }
    }
    return -1
}

function smallestBalancedIndex(nums: number[]): number {
    let s = 0;
    for (const x of nums) {
        s += x;
    }
    for (let i = nums.length - 1, p = 1; i >= 0; --i) {
        s -= nums[i];
        if (s === p) {
            return i;
        }
        p *= nums[i];
        if (p >= s) {
            break;
        }
    }
    return -1;
}

3862. 找出最小平衡下标

题目描述

解法

方法一：枚举

评论