【LeetCode】 724. Find Pivot Index

Description

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.
If the index is on the left edge of the array, then the left sum is 0 because there are no elements to the left. This also applies to the right edge of the array.
Return the leftmost pivot index. If no such index exists, return -1.

給予一個整數陣列 nums，計算它 pivot 的索引值。
pivot 的索引代表他左邊元素的總和剛好等於右邊元素的總和
如果索引在最左邊的邊界，此時左邊總和會是 0 因為沒有任何元素在他左邊了；同樣類推到右邊邊界。
回傳最左邊的 pivot 索引，如果不存在則回傳 -1。

Example:

Example 1:

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


Example 2:

Input: nums = [1,2,3]
Output: -1
Explanation:
There is no index that satisfies the conditions in the problem statement.


Example 3:

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

• 先算出整個陣列的總和，然後遍歷整個陣列，過程中不停計算和比較左總和和右總和
  • 左總和就是遍歷時不停累加上去
  • 右總和是整個陣列的總和不停遞減下去

Code

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int sum = 0;
        for(int i = 0; i < nums.size(); i++)
            sum += nums[i];
        
        int left = 0;
        for(int i = 0; i < nums.size(); i++)
        {
            sum -= nums[i];
            if(left == sum)
                return i;
            left += nums[i];
        }
        return -1;
    }
};

tags: LeetCode C++