前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >一起玩转算法:寻找数组的中心索引

一起玩转算法:寻找数组的中心索引

作者头像
Rouse
发布2021-02-23 15:07:43
3510
发布2021-02-23 15:07:43
举报
文章被收录于专栏:Android补给站Android补给站

算法描述

系数:☆☆

给你一个整数数组nums,请编写一个能够返回数组中心索引的方法。

数组中心索引是数组的一个索引,其左侧所有元素相加的和等于右侧所有元素相加的和。

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

注意:中心索引可能出现在数组的两端。

示例:

代码语言:javascript
复制
输入:nums = [1, 7, 3, 6, 5, 6]
输出:3
解释:
索引 3 (nums[3] = 6) 的左侧数之和 (1 + 7 + 3 = 11),与右侧数之和 (5 + 6 = 11) 相等。
同时, 3 也是第一个符合要求的中心索引。

思路

要符合前段部分的和与后段部分的和相同,我们可以得到以下公式

代码语言:javascript
复制
(总和 - 当前位置值)/ 2 = 当前位置的前段部分的和

有了这个公式,我们的思路也就出来了

  1. 计算出整数数组的总和
  2. 遍历整数数组,累计遍历的和
  3. 带入上面的公式,判断当前索引位置是否符合中心索引
  4. 符合则返回当前的索引,否则继续遍历;如果一直不符合,说明不存在,则返回-1

实现源码

代码语言:javascript
复制
fun solution(nums: IntArray): Int {
    var totalSum = 0 // 总和
    var subSum = 0 // 前段部分的和
    // 计算总和
    for (item in nums) {
        totalSum += item
    }

    nums.forEachIndexed { index, item ->
        // 判断是否为中心索引
        if (subSum * 2 + item == totalSum) {
            return index
        }
        subSum += item
    }

    return -1
}

复杂度分析

  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2021-01-29,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 Android补给站 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 思路
  • 实现源码
  • 复杂度分析
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档