leetcode 724 Find Pivot Index

starsfun 发布于2019-08-15 14:01 / 2081人阅读

摘要：左边的元素和为，刚好等于右边的元素和。在第二趟遍历中，检查当前元素左边所有元素的加和，是否等于减去当前元素的值，如果满足，则当前点为枢纽点，返回当前元素的位置。

题目详情

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. 题目的意思要找出输入数组的“枢纽”点。这个“枢纽”的定义就是，这个元素所有左边的元素的加和刚好等于它所有右边元素的加和，并且我们返回这个枢纽点的位置。如果不存在这样的“枢纽”，则返回－1.如果有多个这样的枢纽，则返回最左侧的枢纽点。
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]作为枢纽点的情况，这种情况下，nums[0]的所有的右边的元素加和应该为0，则nums[0]为数组的枢纽点。

考虑了这个特殊情况就没有什么特别的了。我们先遍历一趟获得数组元素值的和sum。

在第二趟遍历中，检查当前元素左边所有元素的加和，是否等于sum减去当前元素的值，如果满足，则当前点为枢纽点，返回当前元素的位置。

解法

    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

专线服务云服务器 Pivot 724服务器云监控平台 Leetcod LeetCode

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

转载请注明本文地址：https://www.ucloud.cn/yun/68457.html

[LeetCode] 724. Find Pivot Index

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

vibiu 2019-08-16 13:49 评论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