題目描述
給定一個整數類型的數組 nums新思，請編寫一個能夠返回數組“中心索引”的方法极阅。
我們是這樣定義數組中心索引的：數組中心索引的左側所有元素相加的和等于右側所有元素相加的和避凝。
如果數組不存在中心索引朋凉，那么我們應該返回 -1避消。如果數組有多個中心索引下翎，那么我們應該返回最靠近左邊的那一個混稽。
示例 1:
輸入:
nums = [1, 7, 3, 6, 5, 6]
輸出: 3
解釋:
索引3 (nums[3] = 6) 的左側數之和(1 + 7 + 3 = 11)采驻，與右側數之和(5 + 6 = 11)相等。
同時, 3 也是第一個符合要求的中心索引匈勋。
示例 2:
輸入:
nums = [1, 2, 3]
輸出: -1
解釋:
數組中不存在滿足此條件的中心索引礼旅。
說明:
-
nums的長度范圍為[0, 10000]。 - 任何一個
nums[i]將會是一個范圍在[-1000, 1000]的整數洽洁。
第一次提交
class Solution {
public int pivotIndex(int[] nums)
{
int p=0;
for (p = 0; p<=nums.length-1; p++)
{
int sum_left = 0;
int sum_right = 0;
for (int i = 0;i<=p-1;i++)
sum_left += nums[i];
for (int j = p+1;j<=nums.length-1; j++)
sum_right += nums[j];
if (sum_left == sum_right)
return p;
}
return -1;
}
}
這個解答的思路就是暴力破解痘系，遍歷數組中每一個元素，把這個元素左邊所有的元素和求出來饿自，再把這個元素右邊所有的元素和求出來汰翠，比較是否相等≌汛疲可想而知复唤，這個速度是很慢的。
改進
class Solution {
public int pivotIndex(int[] nums)
{
int sum = 0;
for (int num :
nums) {
sum += num;
}
int sum_left = 0;
for (int p = 0; p<nums.length; p++)
{
if (p!=0)
{
sum_left += nums[p-1];
}
int sum_right = sum - nums[p] - sum_left;
if (sum_left == sum_right)
return p;
}
return -1;
}
}
這個是看了別人的解答之后做出的修改烛卧。首先把數組每一個元素累加起來佛纫，得到一個和，然后依然是遍歷數組中的每一個元素，每遍歷一個元素呈宇，就使sum_left加上當前元素的前一個元素好爬，同時右邊元素和等于元素總和減去當前元素再減去左邊元素和，這樣就大大減少了做加法的次數甥啄。比較每一次左邊元素和和右邊元素和存炮，若相等就返回索引值。
感想
說出來不怕大家笑話蜈漓，做了有四五個題了吧僵蛛，都是簡單等級的，這還是第二個獨立做出來的迎变，還是用的暴力破解充尉。不過，跟前兩天不看答案不會下手相比還是有進步的衣形。接下來的題目驼侠，先想出暴力破解的方案，但是不要急著提交谆吴，可能提交了也達不到時間要求倒源，要多思考一下能不能剔除一些情況，簡化計算量句狼。
