Go语言题解LeetCode724寻找数组的中心下标
作者:刘09k11 发布时间:2023-07-09 03:26:01
标签:Go,LeetCode,寻找,数组下标
题目描述
724. 寻找数组的中心下标 - 力扣(LeetCode) (leetcode-cn.com)
给你一个整数数组 nums
,请计算数组的 中心下标 。
数组 中心下标 是数组的一个下标,其左侧所有元素相加的和等于右侧所有元素相加的和。
如果中心下标位于数组最左端,那么左侧数之和视为 0
,因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。
如果数组有多个中心下标,应该返回 最靠近左边 的那一个。如果数组不存在中心下标,返回 -1 。
示例 1:
输入:nums = [1, 7, 3, 6, 5, 6]
输出:3
解释:
中心下标是 3 。
左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ,
右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ,二者相等。
示例 2:
输入:nums = [1, 2, 3]
输出:-1
解释:
数组中不存在满足此条件的中心下标。
示例 3:
输入:nums = [2, 1, -1]
输出:0
解释:
中心下标是 0 。
左侧数之和 sum = 0 ,(下标 0 左侧不存在元素),
右侧数之和 sum = nums[1] + nums[2] = 1 + -1 = 0 。
提示:
1 <= nums.length <= 10^4
-1000 <= nums[i] <= 1000
思路分析
暴力 破解思路 遍历数组每一位,计算出每一位左侧所有值和右侧所有值,然后进行比较。复杂度为 O(n²);
优化暴力 破解
其实遍历时,无需每次都计算所有的值,我们可以利用上一次计算好的值,增减一位即可得到本次的目标值。
[1, 2, 3 ,4 ,5, 6]
遍历1:当前位为1,leftSum[0]=0, rightSum[0]=20;
遍历2:当前位为2,leftSum[1]=leftSum[0]+nums[0] = 1, rightSum[1] = rightSum[0] - nums[1] = 18;
遍历3:当前位为3,leftSum[2]=leftSum[1]+nums[1] = 3, rightSum[2] = rightSum[1] - nums[2] = 15;
........
AC 代码
class Solution {
public int pivotIndex(int[] nums) {
int length = nums.length;
if (length == 0) {
return -1;
}
if (length == 1) {
return 0;
}
// 左右侧的累加值,初始化
int leftSum = 0;
int rightSum = 0;
// 右累加值,从第二位开始累加到最后一位
for (int i=1;i<length;i++) {
rightSum += nums[i];
}
for (int i=0;i<length;i++) {
if (i == 0) {
if (leftSum == rightSum) {
return i;
}
} else {
// 不是第一位,左累加值要加上上一位的数字,右累加值要减去本位的数字
leftSum += nums[i-1];
rightSum -= nums[i];
if (leftSum == rightSum) {
return i;
}
}
}
return -1;
}
}
来源:https://juejin.cn/post/7179621615070609466
0
投稿
猜你喜欢
- 目录本文目标如何使用本教程正则表达式到底是什么?入门测试正则表达式元字符字符转义重复字符类反义替换分组后向引用零宽断言负向零宽断言注释贪婪与
- 最近因工作需要,要在静态页面上实现分页,想了下,决定用AJAX来实现,所以就捣鼓了下面这么个东西,截图如下:更多关于分页的文章演示地址:ht
- 在ie7发布之前,Dean的addEvent/removeEvent可以称的上是完美了。IE7发布后,引入新的内存泄漏(这个我不是很确定,忘
- 一. 网页挂马的概念: 网页挂马是指:在获取网站或者网站服务器的部分或者全部权限后,在网
- 以下是IE7中新支持的属性:min-height,max-height,min-width,max-width这个hack还可以使最大高度兼
- 阅读上一章:[翻译]标记语言和样式手册 Chapter 15 为body指定样式Chapter 16 下一步现在你知道了如何使用标准改进你的
- 这篇文章主要给大家介绍了利用Thinkphp结合ajaxFileUpload实现异步图片传输的方法,文中给出了详细的示例代码,对大家具有一定
- 好多同志对 iframe 是如何控制的,并不是十分了解,基本上还处于一个模糊的认识状态.注意两个事项,ifr 是一个以存在的 iframe
- 又发现一个IE不标准的地方,unshift方法会返回新数组的长度,但IE6与IE7则返回undefined。var a = [3,2,1,4
- Application对象 Application对象是个应用程序级的对象,用来在所有用户间共享信息,并可以在Web应用程序运行期间持久地保
- 在MySQL中,使用auto_increment类型的id字段作为表的主键,并用它作为其他表的外键,形成“主从表结构”,这是数据库设计中常见
- 在默认的情况下,MySQL搜索不区分大小写(但某些字符集始终区分大小写,如czech)。这意味着,如果你使用col_name LIKE
- 1. 游戏是更注重于体验的产品,所以应该将游戏本省做得更加炫动和增加参与感觉。2. 网络游戏和单击游戏的区别在于社会化的添加,所以运用好这样
- 代码如下:<% function CheckFileContent(FileName) dim 
- 我在程序首端添加了On Error Resume Next ,以更好地处理执行时引起的错误,但在数据库访问中引出了麻烦,因为我在一个查询操作
- 如何将123456789转化成123,456,789这样的形式呢?很多流量大的站比如优酷都有这样的格式。也是设计程序最常用的算
- 第七步: 在自定义分页的Repeater 里添加排序功能现在已经完成了自定义分页,我们再来添加排序功能。ProductsBLL类的GetPr
- 方法不是主流的。有一组数据,大概10万个左右,每一单位的值不会大于30000,要求按照由大到小的顺序不重复输出。参考无忧cosin的方法后(
- 先看一段HTML代码,在下边这段代码中,这张图片的宽度未知,我想写在CSS中写一行限制最大宽度为50px:<div id=&
- 在翻译这篇文章时我想起一件事情,去年有个朋友在网上非常兴致勃勃的和我说:“我弄了一个很酷的网站,去玩玩吧!真的不错哦!”,然后他把网址发给我