🍓1. 題目

題目鏈接：724. 尋找數組的中心下標 - 力扣（LeetCode）

給你一個整數數組 nums ，請計算數組的 中心下標 。

數組 中心下標 是數組的一個下標，其左側所有元素相加的和等于右側所有元素相加的和。

如果中心下標位于數組最左端，那么左側數之和視為 0 ，因為在下標的左側不存在元素。這一點對于中心下標位于數組最右端同樣適用。

如果數組有多個中心下標，應該返回 最靠近左邊 的那一個。如果數組不存在中心下標，返回 -1 。

示例 1：

輸入：nums = [1, 7, 3, 6, 5, 6]
輸出：3
解釋：
中心下標是 3 。
左側數之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ，
右側數之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，二者相等。

示例 2：

輸入：nums = [1, 2, 3]
輸出：-1
解釋：
數組中不存在滿足此條件的中心下標。

示例 3：

輸入：nums = [2, 1, -1]
輸出：0
解釋：
中心下標是 0 。
左側數之和 sum = 0 ，（下標 0 左側不存在元素），
右側數之和 sum = nums[1] + nums[2] = 1 + -1 = 0 。

提示：

• 1 <= nums.length <= 104
• -1000 <= nums[i] <= 1000

🫒2. 算法原理

🦄解法一：暴力枚舉

這題的意思就是找到一個所謂的“中間位置”（不包含這個位置），讓其兩邊的和都相等，如果整個數組都找完了，沒有符合的，那么久返回-1，這題定位在簡單級別，直接想法就是暴力枚舉。

遍歷數組，每個中心下標都枚舉出左邊和右邊的元素和，這個時間復雜度為O(N²)，這里就不作示例了。

🦄解法二：前綴和

我們可以用前綴和的思想來優化這個暴力解法

不要笨重的記dp[i] = dp[i-1] + arr[i]模板，根據題目實際需求分析

這里要求一個下標的左邊和右邊的元素，我們可以采用f表示前綴和數組，g表示后綴和數組：

• f[i]表示[0,i-1]區間所有元素的和
  f[i] = f[i-1] + nums[i-1]
• g[i]表示[i+1,n-1]區間所有元素的和
  g[i] = g[i+1] + nums[i+1]

有了前綴和與后綴和數組，我們直接判斷f[i] == g[i]即可

細節問題：

• 初始化：這里是從下標0開始的，那么f[0]就需要特殊處理一下，f[0] = 0；
  同理g[n-1]也是，g[n-1] = 0
• 填表順序：對于f，因為要依賴f[i-1]，所以填表順序為從左向右；
  對于g，要依賴g[i+1]，所以填表順序為從右向左

這個時間復雜度為O(n)+O(n)+O(n)，可理解為O(N)

🥔3. 代碼實現

class Solution {
public:int pivotIndex(vector<int>& nums){int n = nums.size();vector<int> f(n),g(n);//處理前綴和數組for(int i=1;i<n;i++)f[i] = f[i-1] + nums[i-1];//處理后綴和數組for(int i=n-2;i>=0;i--)g[i] = g[i+1] + nums[i+1];//判斷for(int i=0;i<n;i++){if(f[i]==g[i])return i;}return -1;}
};

力扣這個擊敗多少用戶有時候是看網速的，如果算法沒問題，多提交幾次就行了，如果不在意，也可以忽略，沒什么影響。