# Q1. Count Dominant Indices

**練習日期：** 2026-02-08
**類型：** Weekly Contest 488

## 📘 題目敘述

給你一個長度為 `n` 的整數陣列 `nums`。

如果索引 `i` 的元素滿足下列條件，則稱它為 dominant：

`nums[i] > average(nums[i + 1], nums[i + 2], ..., nums[n - 1])`

你的任務是計算有多少個索引 `i` 是 dominant。

一組數字的平均值（average）是把所有數字加總後，再除以數字的總數所得到的值。

注意：任何陣列的最右邊元素都不是 dominant。

### 條件限制

* `1 <= nums.length <= 100`
* `1 <= nums[i] <= 100`

## 🧠 解題思路

我在想這題時，先把題目的比較式換成「比較好算」的樣子。

題目要我檢查每個 `i` 是否滿足：

`nums[i] > average(nums[i+1 ... n-1])`

如果直接算平均值，會出現除法和小數。我不想用浮點數，所以我把它改寫成整數比較。

假設右邊的總和是 `sumRight`，右邊元素個數是 `cntRight = n - i - 1`，那：

`nums[i] > sumRight / cntRight`
等價於
`nums[i] * cntRight > sumRight`

所以我只要能快速拿到每個 `i` 的右側總和 `sumRight`，就能用整數完成判斷。

我的做法是先算整個陣列的總和 `sum`，然後從左到右走時，把目前的 `nums[i]` 從 `sum` 扣掉。扣完之後的 `sum` 就剛好是「右側子陣列」的總和，這樣每個位置都能 O(1) 取得右側總和。

### 所有變數

* `sum`：目前右側子陣列的總和（一開始是整體總和，之後一路扣掉左邊元素）
* `count`：dominant 的索引數量（最後回傳它）

## 🪜 主要流程步驟

### 1. 處理最右邊元素不計算的規則

題目說最右邊元素不是 dominant，所以我後面的檢查只會做到 `n - 2`。如果陣列長度只有 `1`，那沒有任何索引可以成為 dominant，直接回傳 `0`。

---

### 2. 先把整個陣列加總起來

我先用一個迴圈把 `nums` 全部加起來存到 `sum`。這樣後面我就可以透過扣掉左邊元素，快速得到右邊的總和。

---

### 3. 從左到右枚舉每個索引，更新右側總和

我用 `j` 從 `0` 走到 `n - 2`。每次先做 `sum -= nums[j]`，做完後 `sum` 就代表 `nums[j+1] ... nums[n-1]` 的總和，也就是題目要比較的右側子陣列總和。

---

### 4. 用整數形式比較是否大於右側平均

右側子陣列長度是 `n - j - 1`。如果 `(n - j - 1) * nums[j] > sum`，就代表 `nums[j]` 大於右側平均值，因此 `count++`。

---

### 5. 回傳答案

全部掃完後，回傳 `count`。

## 💻 程式碼實作

class Solution {
public:
    int dominantIndices(vector<int>& nums) {
        if (nums.size() == 1) {
            return 0;
        }
        int n = nums.size();
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += nums[i];
        }
        int count = 0;
        for (int j = 0; j < n - 1; j++) {
            sum -= nums[j];
            if ((n - j - 1) * nums[j] > sum) {
                count++;
            }
        }
        return count;
    }
};

## 🔗 題目連結
https://leetcode.com/contest/weekly-contest-488/problems/count-dominant-indices/description/