[LeetCode] 724. Find Pivot Index

vibiu 發布于2019-08-16 13:49 / 3089人閱讀

Problem

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].

Solution

class Solution {
    public int pivotIndex(int[] nums) {
        if (nums == null || nums.length < 3) return -1;
        int n = nums.length;
        int[] dp = new int[n];
        int[] pd = new int[n];
        dp[0] = nums[0];
        pd[n-1] = nums[n-1];
        for (int i = 1; i < n; i++) {
            dp[i] = dp[i-1]+nums[i];
        }
        for (int i = n-2; i >= 0; i--) {
            pd[i] = pd[i+1]+nums[i];
        }
        
        if (pd[1] == 0) return 0;
        for (int i = 1; i < n-1; i++) {
            if (dp[i-1] == pd[i+1]) return i;
        }
        if (dp[n-2] == 0) return n-1;
        
        return -1;
    }
}

GPU云服務器云服務器 Pivot 724服務器云監控平臺 LeetCode LeetCode_String

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/72388.html

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 piv...

starsfun 2019-08-15 14:01 評論0 收藏0
leetcode 部分解答索引（持續更新～）

摘要：前言從開始寫相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫現在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言從開始寫leetcode相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫～現在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。順序整理 1~50 1...

leo108 2019-08-15 14:26 評論0 收藏0
前端 | 每天一個 LeetCode

摘要：在線網站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學習。這篇文章記錄我練習的 LeetCode 題目，語言 JavaScript。在線網站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

張漢慶 2019-08-23 13:42 評論0 收藏0
Wiggle Sort & II

摘要：如果沒復雜度的要求，先也可以，再交叉放入數字也可以。交叉的時候注意是按照，降序的。 Wiggle Sort 題目鏈接：https://leetcode.com/problems... 這道題允許等號，相對簡單，有兩種方法：1. sort然后交換奇數位和它下一位的元素，2. 不滿足條件的時候直接交換可以用遞推來說明一下這么做的正確性：假設到第i位之前都滿足題目要求的關系現在比較...

Moxmi 2019-08-14 17:18 評論0 收藏0
9 .leetcode Peak Index in a Mountain Array

摘要：題目例子我的解法其他解法求最大值然后求二分法查找 1 題目 Lets call an array A a mountain if the following properties hold: A.length >= 3There exists some 0 < i < A.length - 1 such that A[0] < A[1] < ... A[i-1] < A[i] > A[...

txgcwm 2019-08-23 16:56 評論0 收藏0