目錄
題目:
示例:
?分析:
代碼+運(yùn)行結(jié)果:
題目:
示例:
分析:
給一個(gè)數(shù)組,讓我們找出一個(gè)下標(biāo),在這個(gè)下標(biāo)左邊的元素總和等于這個(gè)下標(biāo)右邊的元素總和.
我們可以把整個(gè)數(shù)組的總和求出來,然后再從左往右遍歷一次數(shù)組,遍歷的同時(shí)將遍歷過的數(shù)累加記錄到一個(gè)變量中.若遍歷到一個(gè)數(shù),總和減去它等于遍歷過的累加的總和的兩倍,那么這個(gè)數(shù)就是數(shù)組的中間,它的下標(biāo)就是我們要求的下標(biāo).
?(上圖做錯(cuò)了,但是我懶得改了,右下角方框里應(yīng)該是 (總和-nums[i])/2 == temp) ).
也可以使用前綴和的方法,一樣是用一個(gè)變量來記錄累加的結(jié)果,經(jīng)過三次遍歷,第一次遍歷記錄每個(gè)坐標(biāo)左邊累加的結(jié)果,第二次遍歷記錄每個(gè)坐標(biāo)右邊累加的結(jié)果,第三次遍歷尋找到左右累加結(jié)果一致的坐標(biāo).
代碼+運(yùn)行結(jié)果:
class Solution {
public:
int pivotIndex(vector<int>& nums) {
//統(tǒng)計(jì)總和
int SUM=0,temp=0;
for(const int &num:nums) SUM+=num;
for(int i=0;i<nums.size();i++){
if((SUM-nums[i])/2.0==static_cast<double>(temp)) return i;
temp+=nums[i];
}
return -1;
}
};
文章來源：http://www.zghlxwxcb.cn/news/detail-625738.html
class Solution {
public:
int pivotIndex(vector<int>& nums) {
//前綴和
vector<pair<int,int>>cache(nums.size(),make_pair(0,0));
int temp=0;
for(int i=0;i<nums.size();i++){ //獲取前綴和
cache[i].first=temp;
temp+=nums[i];
}
temp=0;
for(int i=nums.size()-1;i>=0;i--){ //獲取后綴和
cache[i].second=temp;
temp+=nums[i];
}
for(int i=0;i<cache.size();i++){ //若是前綴后綴一致則返回
if(cache[i].first==cache[i].second) return i;
}
return -1;
}
};
文章來源地址http://www.zghlxwxcb.cn/news/detail-625738.html
到了這里，關(guān)于【LeetCode 75】第十九題（724）尋找數(shù)組的中心下標(biāo)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
