leetcode-724-Find Pivot Index

題目描述：

Given an array of integers 

nums

, write a method that returns the "pivot" index of this array.

We define the pivot index as 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 

  nums

   will be in the range 

  [0, 10000]

  .
• Each element 

  nums[i]

   will be an integer in the range 

  [-1000, 1000]

  .

要完成的函數：

int pivotIndex(vector<int>& nums) 

說明：

1、這道題給定一個vector，要求找到vector中的中軸元素。中軸元素的定義是：左邊元素的和等于右邊元素的和。

vector中的元素值在[-1000,1000]之間。

2、這道題不難，我們用類似視窗滑動的想法，從左至右逐個判斷是否是中軸元素就可以了。

代碼如下：（附詳解）

int pivotIndex(vector<int>& nums) 
    {
        int s1=nums.size();
        if(s1==0)return -1;//邊界處理，nums是一個空的vector
        int suml=0,sumr=accumulate(nums.begin(),nums.end(),0)-nums[0],pos=0;//sumr等于從nums[1]開始到末尾的所有元素之和
        while(pos<s1)
        {
            if(suml==sumr)
                return pos;
            pos++;
            suml+=nums[pos-1];//視窗滑動，suml加上一個新的值
            sumr-=nums[pos];//視窗滑動，sumr減去一個值
        }
        return -1;
    }           

複制

上述代碼十分簡潔，實測 43ms，beats 72.02% of cpp submissions。