[LeetCode] 724. Find Pivot Index

vibiu 发布于2019-08-16 13:49 / 3068人阅读

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

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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