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

要完成的函数:

int pivotIndex(vector<int>& nums) 

说明:

1、这道题给定一个vector,要求找到vector中的中轴元素。中轴元素的定义是:左边元素的和等于右边元素的和。

vector中的元素值在[-1000,1000]之间。

2、这道题不难,我们用类似窗口滑动的想法,从左至右逐个判断是否是中轴元素就可以了。

代码如下:(附详解)

    int pivotIndex(vector<int>& nums) 
    {
        int s1=nums.size();
        if(s1==0)return -1;//边界处理,nums是一个空的vector
        int suml=0,sumr=accumulate(nums.begin(),nums.end(),0)-nums[0],pos=0;//sumr等于从nums[1]开始到末尾的所有元素之和
        while(pos<s1)
        {
            if(suml==sumr)
                return pos;
            pos++;
            suml+=nums[pos-1];//窗口滑动,suml加上一个新的值
            sumr-=nums[pos];//窗口滑动,sumr减去一个值
        }
        return -1;
    }

上述代码十分简洁,实测 43ms,beats 72.02% of cpp submissions。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Golang语言社区

Go语言struct类型详解

struct Go语言中,也和C或者其他语言一样,我们可以声明新的类型,作为其它类型的属性或字段的容器。例如,我们可以创建一个自定义类型person代表一个人的...

368120
来自专栏有趣的django

4.自定义序列类

19900
来自专栏公众号_薛勤的博客

详解JSOUP的Select选择器语法

可以使用Element.select(String selector) 和 Elements.select(String selector) 方法实现:

12820
来自专栏咸鱼不闲

jsoup爬虫工具的简单使用

解决方案: 1.通过url 获得doucment对象, 2.调用select()等方法获得Elements对象, 3.调用.text()等方法,获得自己想要的内...

58140
来自专栏飞雪无情的博客

Go语言实战笔记(五)| Go 切片

切片也是一种数据结构,它和数组非常相似,因为他是围绕动态数组的概念设计的,可以按需自动改变大小,使用这种结构,可以更方便的管理和使用数据集合。

12140
来自专栏blackheart的专栏

[C#1] 7-枚举

1.Enum 枚举是定义了一组符号名称和数值对,如下: 1 //byte、sbyte、short、ushort、int、uint、long 或 ulong ...

234100
来自专栏coder修行路

Go基础之--排序和查找操作

排序操作主要都在sort包中,导入就可以使用了 import("sort") 常用的操作 sort.Ints:对整数进行排序 sort.Strings:对字符串...

36990
来自专栏前端说吧

JS-随机div颜色

36170
来自专栏梦魇小栈

JQuery分析及实现part3之属性模块功能及实现

9330
来自专栏Golang语言社区

Go语言编程中字符串切割方法小结

1.func Fields(s string) []string,这个函数的作用是按照1:n个空格来分割字符串最后返回的是 []string的切片 import...

50790

扫码关注云+社区

领取腾讯云代金券