其他系列文章導航
Java基礎(chǔ)合集
數(shù)據(jù)結(jié)構(gòu)與算法合集設(shè)計模式合集
多線程合集
分布式合集
ES合集
文章目錄
其他系列文章導航
文章目錄
前言
一、題目描述
二、題解
2.1 前綴和的解題模板
2.1.1 最長遞增子序列長度
2.1.2 尋找數(shù)組中第 k 大的元素
2.1.3 最長公共子序列長度
2.1.4 尋找數(shù)組中第 k 小的元素
2.2 方法一：前綴和
三、代碼
3.2 方法一：前綴和
四、復雜度分析
4.2 方法一：前綴和
前言
這是力扣的 724 題，難度為簡單，解題方案有很多種，本文講解我認為最奇妙的一種。
這是一道非常經(jīng)典的前綴和問題，雖然看似簡單，但它卻能讓你深入理解前綴和的特點。
一、題目描述
給你一個整數(shù)數(shù)組?nums?，請計算數(shù)組的?中心下標?。
數(shù)組?中心下標?是數(shù)組的一個下標，其左側(cè)所有元素相加的和等于右側(cè)所有元素相加的和。
如果中心下標位于數(shù)組最左端，那么左側(cè)數(shù)之和視為?0?，因為在下標的左側(cè)不存在元素。這一點對于中心下標位于數(shù)組最右端同樣適用。
如果數(shù)組有多個中心下標，應該返回?最靠近左邊?的那一個。如果數(shù)組不存在中心下標，返回?-1?。
示例 1：
輸入：nums = [1, 7, 3, 6, 5, 6] 輸出：3 解釋： 中心下標是 3 。 左側(cè)數(shù)之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ， 右側(cè)數(shù)之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，二者相等。
示例 2：
輸入：nums = [1, 2, 3] 輸出：-1 解釋： 數(shù)組中不存在滿足此條件的中心下標。
示例 3：
輸入：nums = [2, 1, -1] 輸出：0 解釋： 中心下標是 0 。 左側(cè)數(shù)之和 sum = 0 ，（下標 0 左側(cè)不存在元素）， 右側(cè)數(shù)之和 sum = nums[1] + nums[2] = 1 + -1 = 0 。
提示：
1 <= nums.length <= 104-1000 <= nums[i] <= 1000
二、題解
2.1 前綴和的解題模板
前綴和算法是一種在處理數(shù)組或鏈表問題時常用的技巧，它可以有效地減少重復計算，提高算法的效率。下面是一些常見的使用前綴和算法的題目以及解題思路：
2.1.1 最長遞增子序列長度
題目描述：給定一個無序數(shù)組，求最長遞增子序列的長度。
解題思路：可以使用前綴和和單調(diào)棧來解決這個問題。首先，遍歷數(shù)組，計算出前綴和。然后，使用單調(diào)棧記錄當前遞增子序列的起始位置。遍歷數(shù)組時，如果當前元素大于前綴和，說明可以擴展當前遞增子序列，將當前位置入棧。如果當前元素小于等于前綴和，說明當前遞增子序列已經(jīng)結(jié)束，彈出棧頂元素。最后，棧中剩余的元素即為最長遞增子序列的起始位置，計算長度即可。
2.1.2 尋找數(shù)組中第 k 大的元素
題目描述：給定一個無序數(shù)組和一個整數(shù)k，找到數(shù)組中第k大的元素。
解題思路：可以使用前綴和和快速選擇算法來解決這個問題。首先，計算出數(shù)組的前綴和。然后，使用快速選擇算法在數(shù)組中找到第k小的元素。具體實現(xiàn)中，每次選擇一個樞軸元素，將數(shù)組分成兩部分，小于樞軸的元素和大于樞軸的元素。如果樞軸左邊的元素個數(shù)小于k，則在左邊的子數(shù)組中繼續(xù)查找；如果樞軸左邊的元素個數(shù)大于等于k，則在右邊的子數(shù)組中繼續(xù)查找。最后，當找到第k小的元素時，返回該元素即可。
2.1.3 最長公共子序列長度
題目描述：給定兩個字符串，求最長公共子序列的長度。
解題思路：可以使用動態(tài)規(guī)劃算法來解決這個問題。如果字符串長度分別為m和n，則可以定義一個二維數(shù)組dp[m+1][n+1]，其中dp[i][j]表示字符串s1的前i個字符和字符串s2的前j個字符的最長公共子序列長度。根據(jù)動態(tài)規(guī)劃的思想，狀態(tài)轉(zhuǎn)移方程為dp[i][j] = max(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])。如果s1[i-1]等于s2[j-1]，則dp[i][j] = dp[i-1][j-1] + 1；否則dp[i][j]取其他兩種情況中的較大值。最終結(jié)果為dp[m][n]。
2.1.4 尋找數(shù)組中第 k 小的元素
題目描述：給定一個無序數(shù)組和一個整數(shù)k，找到數(shù)組中第k小的元素。
解題思路：可以使用前綴和和快速選擇算法來解決這個問題。具體實現(xiàn)與尋找第k大元素類似，只不過最后返回的是第k小的元素而非第k大的元素。
2.2 方法一：前綴和
題目僅說明是整數(shù)數(shù)組，無其他已知條件，因此考慮直接遍歷數(shù)組。
- 設(shè)索引 i?對應變量「左側(cè)元素相加和 leftSum」和「右側(cè)元素相加和 rightSum」。
- 遍歷數(shù)組 nums ，每輪更新 leftSum 和 rightSum。
- 遍歷中，遇到滿足 leftSum == rightSum 時，說明當前索引為中心下標，返回即可。
- 若遍歷完成，仍未找到「中心下標」，則返回 -1 。
初始化時，相當于索引 i=?1 ，此時 leftSum = 0 , rightSum = 所有元素的和 。
需要考慮大數(shù)越界問題。題目給定整數(shù)數(shù)組 nums ，并給定取值范圍。
題目的范圍在 int 類型的取值范圍內(nèi)，因此 sum_left 和 sum_right 使用 int 類型即可。
三、代碼
3.2 方法一：前綴和
Java版本：
class Solution {
public int pivotIndex(int[] nums) {
int leftSum = 0, rightSum = Arrays.stream(nums).sum();
for (int i = 0; i < nums.length; i++) {
rightSum -= nums[i];
if (leftSum == rightSum) return i;
leftSum += nums[i];
}
return -1;
}
}C++版本：
class Solution {
public:
int pivotIndex(vector<int>& nums) {
int leftSum = 0, rightSum = accumulate(nums.begin(), nums.end(), 0);
for (int i = 0; i < nums.size(); i++) {
rightSum -= nums[i];
if (leftSum == rightSum) return i;
leftSum += nums[i];
}
return -1;
}
};
Python版本：
class Solution:
def pivotIndex(self, nums: List[int]) -> int:
left_sum, right_sum = 0, sum(nums)
for i in range(len(nums)):
right_sum -= nums[i]
if left_sum == right_sum:
return i
left_sum += nums[i]
return -1
Go版本：文章來源：http://www.zghlxwxcb.cn/news/detail-763268.html
package main
func pivotIndex(nums []int) int {
leftSum := 0
rightSum := 0
for _, v := range nums {
rightSum += v
}
for i, v := range nums {
rightSum -= v
if leftSum == rightSum {
return i
}
leftSum += v
}
return -1
}
四、復雜度分析
4.2 方法一：前綴和
時間復雜度 O(N)： 其中 N?為數(shù)組 nums 長度。求和操作使用 O(N) 線性時間，遍歷 nums 最差使用 O(N) 線性時間。
空間復雜度 O(1)： 變量? leftSum ,? rightSum 使用常數(shù)大小空間。文章來源地址http://www.zghlxwxcb.cn/news/detail-763268.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)和算法】尋找數(shù)組的中心下標的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
