Given an array of integers nums, write a method that returns the "pivot" index of this array.
We define the pivot index as the index where the sum of the numbers to the left of the index is equal to the sum of the numbers to the right of the index.
If no such index exists, we should return -1. If there are multiple pivot indexes, you should return the left-most pivot index.
Example 1:
Input:
nums = [1, 7, 3, 6, 5, 6]
Output: 3
Explanation:
The sum of the numbers to the left of index 3 (nums[3] = 6) is equal to the sum of numbers to the right of index 3.
Also, 3 is the first index where this occurs.
Example 2:
Input:
nums = [1, 2, 3]
Output: -1
Explanation:
There is no index that satisfies the conditions in the problem statement.
Note:
The length of nums will be in the range [0, 10000].
Each element nums[i] will be an integer in the range [-1000, 1000].
自己的解法
class Solution {
public int pivotIndex(int[] nums) {
int right = 0;
for (int i = 0; i < nums.length; i++) {
int sumr = 0;
int suml = 0;
for (int j = 0; j < i; j++) {
suml = suml + nums[j];
right = suml;
}
for (int l = i + 1; l < nums.length; l++) {
sumr = sumr + nums[l];
}
if (right == sumr) {
return i;
}
}
return -1;
}
}
假設(shè)我們知道S是數(shù)字的總和昔园，我們?cè)谒饕齣耐亏。如果我們知道索引i左邊的數(shù)字總和夜郁，那么索引右邊的另一個(gè)總和就是S - nums [i] - leftsum翰萨。因此，我們只需要知道leftsum來(lái)檢查索引是否是恒定時(shí)間內(nèi)的樞軸索引。讓我們這樣做：當(dāng)我們迭代候選索引i時(shí)虾啦，我們將保持leftsum的正確值翠霍。
class Solution {
public int pivotIndex(int[] nums) {
int sum = 0, leftsum = 0;
for (int x: nums) sum += x;
for (int i = 0; i < nums.length; ++i) {
if (leftsum == sum - leftsum - nums[i]) return i;
leftsum += nums[i];
}
return -1;
}
}
