题目描述
- Given an array of integers
nums, write a method that returns the"pivot" indexof this array. - We define the
pivot indexas 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
numswill be in the range[0, 10000]. - Each element
nums[i]will be an integer in the range[-1000, 1000].
解题思路
此题目要求我们找出数组的 中心索引 ，也就是说，数组中心索引的左侧所有元素相加的和等于右侧所有元素相加的和。如果数组不存在中心索引，那么我们应该返回 -1。如果数组有多个中心索引，那么我们应该返回最靠近左边的那一个。
- 遍历整个数组，每判断一个数组元素时，分别计算其左右两侧的元素相加的和。
- 如果相等，则返回此数组元素的索引，否则继续查找。
- 若数组遍历完毕后仍没有找到，则返回
-1。
参考代码
示例代码一
//C++
class Solution {
public:
int pivotIndex(vector<int>& nums)
{
int Lsum, Rsum;
int count = nums.size();
for (int i = 0; i < count; i++)
{
Lsum = Rsum = 0;
for (int j = 0; j < i; j++)
{
Lsum += nums[j];
}
for (int j = i + 1; j < count; j++)
{
Rsum += nums[j];
}
if (Lsum == Rsum)
return i;
}
return -1;
}
};
示例代码二
//C++
class Solution {
public:
int pivotIndex(vector<int>& nums)
{
int Lsum = 0, Rsum = accumulate(nums.begin(),nums.end(),0);
int count = nums.size();
for (int i = 0; i < count; i++)
{
Rsum -= nums[i];
if (Lsum == Rsum)
return i;
Lsum += nums[i];
}
return -1;
}
};
本文由 机灵鹤 SmartCrane 创作
本站文章所有原创文章, 转载前请务必署名
最后编辑时间为: 2018-09-19 23:20