###### tags: `Leetcode` `easy` `array` `prefix sum` `python` `c++`

# 724. Find Pivot Index

## [題目連結:] https://leetcode.com/problems/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```.

**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

## 解題想法:
* 題目給一個整數陣列，計算pivot的索引值。
* pivot的索引代表他左邊元素的總和剛好等於右邊元素的總和

## Python: Sol1_土法煉鋼
* 分別求每個位置之左右

class Solution(object):
    def pivotIndex(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        #ex:[1 , 7, 3, 6, 5, 6]
        #l :[0 , 1, 8,11,17,22]
        #r :[27,20,17,11, 6, 0]
        n=len(nums)
        left=[0 for _ in range(n)]
        right=[0 for _ in range(n)]
        for i in range(1,n):
            left[i]=left[i-1]+nums[i-1]
        for j in range(n-2,-1,-1):
            right[j]=right[j+1]+nums[j+1]
        for pos in range(n):
            if left[pos]==right[pos]:
                return pos
        return -1

## Python: Sol2_快速解
* 先算出整個陣列的總和，利用先前的和:
* 左總為正常遍歷時累加
* 右總為總和遞減當前位置

class Solution(object):
    def pivotIndex(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        total=0
        for i in range(len(nums)):
            total+=nums[i]
        left=0
        right=total
        for pos in range(len(nums)):
            #最左邊一開始left=0
            right-=nums[pos] 
            if left==right:
                return pos
            #比較完要到下一個位置前再加
            left+=nums[pos]
        return -1

if __name__=='__main__':
    result=Solution()
    ans=result.pivotIndex(nums = [1,7,3,6,5,6])
    print(ans)

## C++:

#include<iostream>
#include<vector>
using namespace std;

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

int main(){
    Solution res;
    vector<int> nums={1,7,3,6,5,6};
    int ans=res.pivotIndex(nums);
    cout<<ans<<endl;
    return 0;
}