文档章节

找到数组中左右两边的和相等的pivot的下标 Find Pivot Index

叶枫啦啦
 叶枫啦啦
发布于 2018/01/17 10:06
字数 308
阅读 21
收藏 0

问题:

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

解决:

①  找到左右两边的和相等的pivot的下标,如果有多个,则返回最左侧,如果不存在,返回-1.

class Solution { //34ms
    public int pivotIndex(int[] nums) {
        int sum = 0;
        for (int n : nums){
            sum += n;
        }
        int cursum = 0;
        for (int i = 0;i < nums.length;i ++){
            if (sum - nums[i] == 2 * cursum) return i;
            cursum += nums[i];
        }
        return -1;
    }
}

© 著作权归作者所有

共有 人打赏支持
叶枫啦啦
粉丝 13
博文 569
码字总数 354997
作品 0
海淀
私信 提问
Java中的排序

以前总结过排序的种种知识 那么在Java中的Arrays.sort()是如何写的呢? JDK5中的Arrays.sort(int[]) JDK5基本类型的排序是使用优化了的快速排序,我们来看看JDK5中的优化点 /** * 将指定范围...

Hosee
2016/04/04
140
0
快速排序算法QuickSort

1.说明 快速排序法(quicksort)是目前所公认最快的排序方法之一(视解题的对象而定),虽然快速排序法在最差状况下可以达O(n2),但是在多数的情况下,快速排序法的效率表现是相当不错的。快...

嗯哼9925
2017/12/14
0
0
LeetCode 33-Search in Rotated Sorted Array

Problem description Solution Self 看到这个题目,头脑中第一个蹦出来的就是找到rotated的元素,然后两边分别做binary search就可以了。 第一版代码 分两步:1:找到pivot,就是rotated的那...

Quan全
2018/06/21
0
0
在旋转数组中搜索

原题   Suppose a sorted array is rotated at some pivot unknown to you beforehand.   (i.e., might become ).   You are given a target value to search. If found in the array......

一贱书生
2016/12/14
1
0
分分钟掌握快速排序(Java / Scala 实现)

今天我们来学习一种不浪费空间、效率还非常高的排序算法——快速排序。 算法思想 快速排序的基本思想——分治法。 1. 选取基准数(pivot):选数组中的第一个或者中间一个。 2. 分区:将数组...

Jackson_Mu
2014/12/30
0
9

没有更多内容

加载失败,请刷新页面

加载更多

创建多个git账号

实习开发中我们可能一个机子上配置多个git账号,如github.com,oschina.com 或者工作账号,私人账号,这时候就2个账号用一个key,肯定会冲突,有一个会提示没权限(账号和密码对应不上) ssh ...

echojson
29分钟前
1
0
rabbitmq安装教程

RabbitMQ有Windows与Linux版本的,这里先写Windows版本的安装。 以前安装软件总是在百度上找某某安装教程,结果能按照教程安装好的软件真的不多。想起先前以为大牛说的一句话,去官网按照官网...

em_aaron
今天
7
0
Android 贝塞尔曲线实践——波浪式运动

一、波浪效果如下 贝塞尔曲线自定义波浪效果的案例很多,同样方法也很简单,大多数和本案例一样使用二次贝塞尔曲线实现,同样还有一种是PathMeasure的方式,这里我们后续补充,先来看贝塞尔曲...

IamOkay
今天
3
0
Nmap之防火墙/IDS逃逸

选项 解释 -f 报文分段 --mtu 指定偏移大小 -D IP欺骗 -sI 原地址欺骗 --source-port 源端口欺骗 --data-length 指定发包长度 --randomize-hosts 目标主机随机排序 --spoof-mac Mac地址欺骗 ...

Frost729
今天
2
0
带你搭一个SpringBoot+SpringData JPA的环境

不知道大家对SpringBoot和Spring Data JPA了解多少,如果你已经学过Spring和Hibernate的话,那么SpringBoot和SpringData JPA可以分分钟上手的。 其实我在学完SpringBoot和SpringData JPA了之...

java菜分享
今天
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部