Q2. Find the Smallest Balanced Index

📘 題目敘述

你會拿到一個整數陣列 nums。索引 i 是 balanced 當且僅當：左邊元素總和等於右邊元素乘積。左側空集合總和視為 0，右側空集合乘積視為 1。

請回傳最小 balanced index，不存在則回傳 -1。

條件限制

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9

🧠 解題思路

維護兩個累積量：l（左側總和）與 r（右側乘積）。先計算總和後，從右往左推進，每一步都可 O(1) 檢查是否平衡。

另外加入剪枝：若 r > l，後續只會更不可能相等，可直接回傳 -1。

所有變數

• l：左側總和
• r：右側乘積
• n：陣列長度

🪜 主要流程步驟

1. 邊界處理

nums.size() <= 1 時直接回傳 -1。

2. 初始化 l/r

先把所有元素加總到 l，r 初始為 1，並先檢查 index n-1。

3. 從右往左更新並檢查

每次更新 r *= nums[j] 與 l -= nums[j-1]，比較 l == r，若成立回傳對應索引。

4. 未找到則回傳

依目前程式碼最後回傳 l。

⏱️ 複雜度

• 時間複雜度：O(n)
• 空間複雜度：O(1)

💻 程式碼實作

class Solution {
public:
    int smallestBalancedIndex(vector<int>& nums) {
        if (nums.size() <= 1) {
            return -1;
        }
        long long l = 0, r = 1;
        for (int i : nums) {
            l += i;
        }
        int n = nums.size();
        l -= nums[n - 1];
        if (l == r) {
            return n - 1;
        }
        for (int j = n - 1; j > 0; j--) {
            r *= nums[j];
            l -= nums[j - 1];
            if (l == r) {
                return j - 1;
            } else if (r > l) {
                return -1;
            }
        }
        return l;
    }
};

🔗 題目連結

https://leetcode.com/contest/weekly-contest-492/problems/find-the-smallest-balanced-index/