Problem
https://leetcode.com/problems/find-pivot-index/?envType=study-plan&id=level-1
Given an array of integers nums, calculate the pivot index of this array.
The pivot index is the index where the sum of all the numbers strictly to the left of the index is equal to the sum of all the numbers strictly to the index’s right.
Example
Input: nums = [1,7,3,6,5,6]
Output: 3
Explanation:
The pivot index is 3.
Left sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11
Right sum = nums[4] + nums[5] = 5 + 6 = 11
Input: nums = [1,2,3]
Output: -1
Explanation:
There is no index that satisfies the conditions in the problem statement.
Input: nums = [2,1,-1]
Output: 0
Explanation:
The pivot index is 0.
Left sum = 0 (no elements to the left of index 0)
Right sum = nums[1] + nums[2] = 1 + -1 = 0
Solution
c++
Brutle force
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
int pivotIndex(vector<int>& nums) {
int len = nums.size();
int ret = -1;
for(int i = 0; i < len; i++) {
int left = 0;
for (int j = 0; j < i; j++) {
left += nums[j];
}
int right = 0;
for (int k = i+1; k < len; k++) {
right += nums[k];
}
if (left == right) {
ret = i;
break;
}
}
return ret;
}
};
Official
优化思路，知道leftSum，可以通过只计算一次的sum计算出rightSum, 同时leftSum可以通过累加来缓存计算
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
int pivotIndex(vector<int>& nums) {
int len = nums.size();
int sum = 0;
for (int i = 0; i< len; i++) {
sum += nums[i];
}
int ret = -1;
int left = 0;
for(int i = 0; i < len; i++) {
int right = sum - left - nums[i];
if (left == right) {
ret = i;
break;
}
left += nums[i];
}
return ret;
}
};