724. Find Pivot Index

问题:

求给定数组的对称轴index。(其左边元素之和=右边元素之和)

若不存在则返回-1,若存在多个,返回最左边的对称轴。

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].

  

解法:

首先求出所有元素之和 rightsum

再从0开始遍历数组,求 leftsum

rightsum-=nums[i]

如果leftsum==rightsum,则返回 i,

循环结束,返回-1。

 

代码参考:

 1 auto fastio = []() {  //加速方法:去掉io绑定和不需要的功能。这里用到了c++11的Lambda
 2     ios::sync_with_stdio(0);
 3     cin.tie(NULL), cout.tie(NULL);
 4     return 0;
 5 }();
 6 
 7 class Solution {
 8 public:
 9     int pivotIndex(vector<int>& nums) {
10         int leftsum=0, rightsum=0;
11         for(int i:nums) rightsum+=i;
12         for(int i=0; i<nums.size(); i++){
13             rightsum-=nums[i];
14             if(leftsum==rightsum) return i;
15             leftsum+=nums[i];
16         }
17         return -1;
18     }
19 };

 

另一种方法,

leftsum*2==sum-nums[i]

以此判断中轴。

 1 class Solution {
 2 public:
 3     int pivotIndex(vector<int>& nums) {
 4         int leftsum=0, sum=0;
 5         for(int i:nums) sum+=i;
 6         for(int i=0; i<nums.size(); i++){
 7             if(leftsum*2==sum-nums[i]) return i;
 8             leftsum+=nums[i];
 9         }
10         return -1;
11     }
12 };

 

参考:

加速方法解释:https://blog.csdn.net/qq_32320399/article/details/81518476

上一篇:快速排序的几种实现方式


下一篇:MYSQL 行转列 Pivot 动态 思路