[LeetCode] 724. Find Pivot Index

vibiu 發(fā)布于2019-08-16 13:49 / 3090人閱讀

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云服務(wù)器云服務(wù)器 Pivot 724服務(wù)器云監(jiān)控平臺(tái) LeetCode LeetCode_String

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/72388.html

相關(guān)文章

leetcode 724 Find Pivot Index

摘要：左邊的元素和為，剛好等于右邊的元素和。在第二趟遍歷中，檢查當(dāng)前元素左邊所有元素的加和，是否等于減去當(dāng)前元素的值，如果滿(mǎn)足，則當(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 piv...

starsfun 2019-08-15 14:01 評(píng)論0 收藏0
leetcode 部分解答索引（持續(xù)更新～）

摘要：前言從開(kāi)始寫(xiě)相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒(méi)有按順序?qū)懍F(xiàn)在翻起來(lái)覺(jué)得蠻亂的?？赡艽蠹铱粗卜浅２环奖?。所以在這里做個(gè)索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言從開(kāi)始寫(xiě)leetcode相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒(méi)有按順序?qū)憽F(xiàn)在翻起來(lái)覺(jué)得蠻亂的?？赡艽蠹铱粗卜浅２环奖恪Ｋ栽谶@里做個(gè)索引嘻嘻。順序整理 1~50 1...

leo108 2019-08-15 14:26 評(píng)論0 收藏0
前端 | 每天一個(gè) LeetCode

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

張漢慶 2019-08-23 13:42 評(píng)論0 收藏0
Wiggle Sort & II

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

Moxmi 2019-08-14 17:18 評(píng)論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 評(píng)論0 收藏0