Medium

题目描述

给你一个整数数组 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^5
  • 1 <= nums[i] <= 10^9

解题思路

解题思路

这道题要求找到一个索引 i，使得左侧元素的和等于右侧元素的乘积。我们需要分别计算每个位置的左侧和与右侧乘积。

方法一：前缀和 + 后缀乘积

  1. 预处理前缀和：计算每个位置左侧所有元素的和
  2. 预处理后缀乘积：计算每个位置右侧所有元素的乘积
  3. 逐一检查：从左到右检查每个索引是否平衡

关键注意点：

  • 左侧没有元素时，和为 0
  • 右侧没有元素时，乘积为 1
  • 需要处理数值溢出问题，当右侧乘积过大时可以提前剪枝

方法二：优化的一次遍历

为了处理大数乘积可能的溢出问题，可以在计算过程中进行溢出检查。当右侧乘积超过可能的最大左侧和时，可以提前判断该位置及后续位置不可能平衡。

推荐使用方法一，因为实现简洁且在大多数情况下效率良好。

代码实现

class Solution {
public:
    int smallestBalancedIndex(vector<int>& nums) {
        int n = nums.size();
        
        // 计算前缀和
        vector<long long> prefixSum(n + 1, 0);
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }
        
        // 计算后缀乘积
        vector<long long> suffixProduct(n + 1, 1);
        for (int i = n - 1; i >= 0; i--) {
            suffixProduct[i] = suffixProduct[i + 1] * nums[i];
            // 防止溢出
            if (suffixProduct[i] > 1e18) {
                suffixProduct[i] = 1e18;
            }
        }
        
        // 检查每个索引
        for (int i = 0; i < n; i++) {
            long long leftSum = prefixSum[i];
            long long rightProduct = suffixProduct[i + 1];
            
            if (leftSum == rightProduct) {
                return i;
            }
        }
        
        return -1;
    }
};

class Solution:
    def smallestBalancedIndex(self, nums: list[int]) -> int:
        n = len(nums)
        
        # 计算前缀和
        prefix_sum = [0] * (n + 1)
        for i in range(n):
            prefix_sum[i + 1] = prefix_sum[i] + nums[i]
        
        # 计算后缀乘积
        suffix_product = [1] * (n + 1)
        for i in range(n - 1, -1, -1):
            suffix_product[i] = suffix_product[i + 1] * nums[i]
            # 防止溢出
            if suffix_product[i] > 10**18:
                suffix_product[i] = 10**18
        
        # 检查每个索引
        for i in range(n):
            left_sum = prefix_sum[i]
            right_product = suffix_product[i + 1]
            
            if left_sum == right_product:
                return i
        
        return -1

public class Solution {
    public int SmallestBalancedIndex(int[] nums) {
        int n = nums.Length;
        
        // 计算前缀和
        long[] prefixSum = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }
        
        // 计算后缀乘积
        long[] suffixProduct = new long[n + 1];
        suffixProduct[n] = 1;
        for (int i = n - 1; i >= 0; i--) {
            suffixProduct[i] = suffixProduct[i + 1] * nums[i];
            // 防止溢出
            if (suffixProduct[i] > 1e18) {
                suffixProduct[i] = (long)1e18;
            }
        }
        
        // 检查每个索引
        for (int i = 0; i < n; i++) {
            long leftSum = prefixSum[i];
            long rightProduct = suffixProduct[i + 1];
            
            if (leftSum == rightProduct) {
                return i;
            }
        }
        
        return -1;
    }
}

var smallestBalancedIndex = function(nums) {
    const n = nums.length;
    
    for (let i = 0; i < n; i++) {
        let leftSum = 0;
        let rightProduct = 1;
        
        // Calculate left sum
        for (let j = 0; j < i; j++) {
            leftSum += nums[j];
        }
        
        // Calculate right product
        for (let j = i + 1; j < n; j++) {
            rightProduct *= nums[j];
        }
        
        if (leftSum === rightProduct) {
            return i;
        }
    }
    
    return -1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n)
空间复杂度O(n)

其中 n 是数组 nums 的长度。我们需要遍历数组两次来计算前缀和和后缀乘积，然后再遍历一次来检查平衡索引，总时间复杂度为 O(n)。空间复杂度为 O(n)，用于存储前缀和和后缀乘积数组。