Go语言题解LeetCode724寻找数组的中心下标
作者:刘09k11 时间:2023-07-09 03:26:01
题目描述
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
标签:Go,LeetCode,寻找,数组下标
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
python代码中怎么换行
2023-04-07 10:46:45
Python中lambda的用法及其与def的区别解析
2021-09-22 13:59:03
Python制作进度条的几种方法
2022-03-11 05:36:23
![](https://img.aspxhome.com/file/2023/5/117625_0s.jpg)
基于Php mysql存储过程的详解
2024-06-05 09:22:00
MYSQL实现连续签到功能断签一天从头开始(sql语句)
2024-01-22 16:35:11
![](https://img.aspxhome.com/file/2023/7/126257_0s.png)
pytest实现多进程与多线程运行超好用的插件
2023-03-23 15:56:23
![](https://img.aspxhome.com/file/2023/0/99510_0s.jpg)
Python将字符串常量转化为变量方法总结
2023-07-14 00:36:58
js函数setTimeout延迟执行的简单介绍
2024-05-05 09:15:14
sql2005 HashBytes 加密函数
2024-01-21 11:28:23
使用Python对接OpenAi API实现智能QQ机器人的方法
2023-08-12 10:24:25
![](https://img.aspxhome.com/file/2023/2/121142_0s.png)
Python的基本语法详解
2022-10-27 22:38:42
利用Python将图片中扭曲矩形的复原
2022-05-24 21:35:54
![](https://img.aspxhome.com/file/2023/3/95233_0s.jpg)
Python与C++中梯度方向直方图的实现
2022-03-17 20:37:34
![](https://img.aspxhome.com/file/2023/5/117285_0s.jpg)
Python 字符串操作(string替换、删除、截取、复制、连接、比较、查找、包含、大小写转换、分割等)
2021-01-12 08:30:45
Oracle跨数据库查询并插入实现原理及代码
2024-01-14 18:52:58
查询SQL Server Index上次Rebuild时间的方法
2024-01-14 11:31:23
pyspark操作MongoDB的方法步骤
2021-05-02 11:12:12
![](https://img.aspxhome.com/file/2023/5/82825_0s.jpg)
pandas 选取行和列数据的方法详解
2022-12-29 19:28:58
![](https://img.aspxhome.com/file/2023/1/124761_0s.png)
mysql数据库实现设置字段长度
2024-01-24 12:49:13
MySql 8.0.11安装配置教程
2024-01-18 23:41:46
![](https://img.aspxhome.com/file/2023/2/68592_0s.png)