LeetCode如何解决数组中心索引问题

这篇文章主要介绍LeetCode如何解决数组中心索引问题,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们一定要看完!

成都创新互联-专业网站定制、快速模板网站建设、高性价比铜官网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式铜官网站制作公司更省心,省钱,快速模板网站建设找我们,业务覆盖铜官地区。费用合理售后完善,10余年实体公司更值得信赖。

题目描述:

给定一个整数类型的数组 nums,请编写一个能够返回数组 “中心索引” 的方法。

中心索引 :数组中心索引的左侧所有元素相加的和等于右侧所有元素相加的和。

如果数组不存在中心索引,那么我们应该返回 -1。如果数组有多个中心索引,那么我们应该返回最靠近左边的那一个

示例:

输入:nums = [1, 7, 3, 6, 5, 6]输出:3解释:索引 3 (nums[3] = 6) 的左侧数之和 (1 + 7 + 3 = 11),与右侧数之和 (5 + 6 = 11) 相等。同时, 3 也是第一个符合要求的中心索引
输入:nums = [1, 2, 3]输出:-1解释:数组中不存在满足此条件的中心索引

说明:

  • nums 的长度范围为 [0, 10000]

  • 任何一个 nums[i] 将会是一个范围在 [-1000, 1000]的整数

LeetCode如何解决数组中心索引问题  


 

 

第一次尝试

想法:利用一个index标号从数组头开始移动,设置left_nums和right_nums两个参数计算左边和右边和

注意:

  • left_nums和right_nums要在循环中,因为每一次要重置

  • 数组可能存在负数,所以也可能存在第一个元素或最后一个元素是中心索引

LeetCode如何解决数组中心索引问题

运行结果:

LeetCode如何解决数组中心索引问题

由于循环太多,导致时间效率较低LeetCode如何解决数组中心索引问题LeetCode如何解决数组中心索引问题LeetCode如何解决数组中心索引问题

本文由“壹伴编辑器”提供技术支持

 

第一次优化

减少循环:灵活利用数组切片

内存参数减少了,空间消耗减小,但是时间效率依然较低

LeetCode如何解决数组中心索引问题

LeetCode如何解决数组中心索引问题

本文由“壹伴编辑器”提供技术支持

 

最终优化方法

思路:若index是中心索引,则左边和=右边和,这样的话可以引入公式:

S(数组总和)= left_nums(左边和)*2 + nums[index]

故只需要动态计算左边和left_nums即可(又减少了一个参数)

动态计算:先判断是否是中心索引,再移动index,并计算左边和left_nums即可

特殊现象:左边和left_nums和索引标号的移动是同步的,当索引标号右移动一位时,left_nums也就加上上一个索引对应的值

LeetCode如何解决数组中心索引问题

LeetCode如何解决数组中心索引问题


以上是“LeetCode如何解决数组中心索引问题”这篇文章的所有内容,感谢各位的阅读!希望分享的内容对大家有帮助,更多相关知识,欢迎关注创新互联行业资讯频道!


分享标题:LeetCode如何解决数组中心索引问题
网站URL:http://myzitong.com/article/pjsppp.html