尋找數組的中心下標，鏈接奉上

暴力循環

???????思路：

依舊是我們的老朋友，暴力循環。
1.可以利用外層for循環，循環變量為數組下標，在循環內分別求出下標左邊與右邊的sum
2.在邊界時討論，
當下標為左邊界（nums[0]）時，left sum=0；當下標為右邊界（nums[numsSize-1）時，right sum=0
3.討論完特殊情況后，進行左邊與右邊的比較；
左==右時，即代表我們找到了下標；
否則返回-1。

代碼實現：

int pivotIndex(int* nums, int numsSize)
{for(int i=0;i<numsSize;i++)//外層for循環{int Lsum=0;//left sum的縮寫。//在循環內部放置是因為防止這次的lsum加上上次的lsum，造成計算錯誤。if(i==0)//特殊情況，左邊界Lsum=0;elsefor(int j=0;j<i;j++)//求lsum的值Lsum+=nums[j];int Rsum=0;if(i==numsSize-1)Rsum=0;elsefor(int j=i+1;j<numsSize;j++)Rsum+=nums[j];if(Lsum==Rsum)return i;}return -1;
}

但是，此種方法的時間復雜度巨大無比，我們可以進行改進

我們發現，每次進入for循環內時，總是會有重復的計算出現，比如：
計算i=0時的Rsum（ringt sum縮寫），每次都重新計算了一遍，但是我們可以在上一次的基礎上進行減nums[i]，大大降低了計算量。

代碼實現：

int pivotIndex(int* nums, int numsSize)
{int i=0;int j=0;int Lsum=0;int Rsum=0;for(i=0;i<numsSize;i++)//首先計算出Rsum的值，i=0時{Rsum+=nums[i];}for(i=0;i<numsSize;i++){if(i==0)Lsum=0;elseLsum+=nums[i-1];//上一次的基礎上加上nums[i-1]if(i==numsSize-1)Rsum=0;elseRsum-=nums[i];//上一次的基礎上減上nums[i]if(Lsum==Rsum)return i;}return -1;
}

但是這樣每次進循環都會判斷一次是否在邊界處
則可以在外部進行判斷

int pivotIndex(int* nums, int numsSize)
{int i=0;int j=0;int Lsum=0;int Rsum=0;for(i=1;i<numsSize;i++)Rsum+=nums[i];if(Lsum==Rsum)return 0;for(i=1;i<numsSize;i++){Lsum+=nums[i-1];Rsum-=nums[i];if(Lsum==Rsum)return i;}return -1;
}

前綴和

思路：

當找到下標時，意味著左右元素和相等。
設數組和為total，則total==Rsum+Lsum+nums[i]
又因左右相等，故total=＝2Rsum+nums[i]

代碼實現：

int pivotIndex(int* nums, int numsSize)
{int total=0;int Rsum=0;for(int i=0;i<numsSize;i++){total+=nums[i];}for(int i=0;i<numsSize;i++){if(Rsum*2+nums[i]==total)return i;Rsum+=nums[i];}return -1;
}

歡迎討論哦