給定一個(gè)整數(shù)類型的數(shù)組 nums踏拜，請編寫一個(gè)能夠返回?cái)?shù)組“中心索引”的方法荧飞。
我們是這樣定義數(shù)組中心索引的：數(shù)組中心索引的左側(cè)所有元素相加的和等于右側(cè)所有元素相加的和亡蓉。
如果數(shù)組不存在中心索引般此，那么我們應(yīng)該返回 -1跷车。如果數(shù)組有多個(gè)中心索引区丑，那么我們應(yīng)該返回最靠近左邊的那一個(gè)拧粪。
示例 1:
輸入:
nums = [1, 7, 3, 6, 5, 6]
輸出: 3
解釋:
索引3 (nums[3] = 6) 的左側(cè)數(shù)之和(1 + 7 + 3 = 11)，與右側(cè)數(shù)之和(5 + 6 = 11)相等沧侥。
同時(shí), 3 也是第一個(gè)符合要求的中心索引可霎。
示例 2:
輸入:
nums = [1, 2, 3]
輸出: -1
解釋:
數(shù)組中不存在滿足此條件的中心索引。
我的解法：遍歷數(shù)組宴杀，對(duì)數(shù)組左右兩邊相加對(duì)比癣朗，應(yīng)該是復(fù)雜度最高的解法
代碼如下:
class Solution {
public int pivotIndex(int[] nums) {
for (int i=0; i<nums.length; i++) {
int sumLeft = 0;
int sumRight = 0;
for (int j = 0; j < i; j++) {
sumLeft += nums[j];
}
for (int k=i+1; k<nums.length; k++) {
sumRight += nums[k];
}
if (sumLeft == sumRight) {
return i;
}
}
return -1;
}
}
別人的方法：解決思路，求得數(shù)組總和旺罢，再遍歷數(shù)組
class Solution {
public int pivotIndex(int[] nums) {
int amount = 0 ;
for(int i=0;i < nums.length;i++){
amount = amount +nums[i];
}
int left = 0;
int right = amount;
for(int i=0;i < nums.length;i++){
right -= nums[i];
if (left == right){
return i;
}
left += nums[i];
}
return -1;
}
}
優(yōu)化后的方法
class Solution {
public int pivotIndex(int[] nums) {
int sum = 0;
int left = 0;
int right = 0;
for(int i:nums){
sum += i;
}
for(int i = 0; i < nums.length; i++){
if(i == 0){
left = 0;
}else{
left += nums[i-1];
}
right = sum - left - nums[i];
if(left == right)
return i;
}
return -1;
}
}
