leetcode 724 Find Pivot Index

starsfun 發(fā)布于2019-08-15 14:01 / 2190人閱讀

摘要：左邊的元素和為，剛好等于右邊的元素和。在第二趟遍歷中，檢查當(dāng)前元素左邊所有元素的加和，是否等于減去當(dāng)前元素的值，如果滿足，則當(dāng)前點(diǎn)為樞紐點(diǎn)，返回當(dāng)前元素的位置。

題目詳情

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. 題目的意思要找出輸入數(shù)組的“樞紐”點(diǎn)。這個(gè)“樞紐”的定義就是，這個(gè)元素所有左邊的元素的加和剛好等于它所有右邊元素的加和，并且我們返回這個(gè)樞紐點(diǎn)的位置。如果不存在這樣的“樞紐”，則返回－1.如果有多個(gè)這樣的樞紐，則返回最左側(cè)的樞紐點(diǎn)。
Example 1:
Input: 
nums = [1, 7, 3, 6, 5, 6]
Output: 3
Explanation: 
nums[3]左邊的元素和為11，剛好等于nums[3]右邊的元素和。
Example 2:
Input: 
nums = [1, 2, 3]
Output: -1
Explanation: 
沒有滿足“樞紐”定義的元素。所以返回－1.

想法

有一種臨界情況需要考慮，就是元素nums[0]作為樞紐點(diǎn)的情況，這種情況下，nums[0]的所有的右邊的元素加和應(yīng)該為0，則nums[0]為數(shù)組的樞紐點(diǎn)。

考慮了這個(gè)特殊情況就沒有什么特別的了。我們先遍歷一趟獲得數(shù)組元素值的和sum。

在第二趟遍歷中，檢查當(dāng)前元素左邊所有元素的加和，是否等于sum減去當(dāng)前元素的值，如果滿足，則當(dāng)前點(diǎn)為樞紐點(diǎn)，返回當(dāng)前元素的位置。

解法

    public int pivotIndex(int[] nums) {
        int length = nums.length;
        if(length == 0 || length ==1)return -1;
        int sum = 0;
        
        for(int num : nums)sum += num;
        
        if(sum-nums[0] == 0)return 0;
        int left = 0;
        for(int i=1;i