📘 題目敘述
給你一個長度為 n 的整數陣列 nums。
如果索引 i 的元素滿足下列條件，則稱它為 dominant：
nums[i] > average(nums[i + 1], nums[i + 2], ..., nums[n - 1])
你的任務是計算有多少個索引 i 是 dominant。
一組數字的平均值（average）是把所有數字加總後，再除以數字的總數所得到的值。
注意：任何陣列的最右邊元素都不是 dominant。
條件限制
1 <= nums.length <= 1001 <= 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/