问题:
求给定数组的对称轴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