【leetCode】leetCode刷题Golang版本--寻找数组的中心索引
< 返回列表时间: 2020-08-07来源:OSCHINA
寻找数组的中心索引
给定一个整数类型的数组 nums ,请编写一个能够返回数组 “中心索引” 的方法。
我们是这样定义数组 中心索引 的:数组中心索引的左侧所有元素相加的和等于右侧所有元素相加的和。
如果数组不存在中心索引,那么我们应该返回 -1。如果数组有多个中心索引,那么我们应该返回最靠近左边的那一个。
示例 1: 输入: nums = [1, 7, 3, 6, 5, 6] 输出: 3 解释: 索引 3 (nums[3] = 6) 的左侧数之和 (1 + 7 + 3 = 11),与右侧数之和 (5 + 6 = 11) 相等。 同时, 3 也是第一个符合要求的中心索引。
示例 2: 输入: nums = [1, 2, 3] 输出: -1 解释: 数组中不存在满足此条件的中心索引。

说明: nums 的长度范围为 [0, 10000] 。 任何一个 nums[i] 将会是一个范围在 [-1000, 1000] 的整数。 解题过程: 注意: 1.中间索引可以为 "len-1" 或者 "0" 2.有多个中间索引时,取最左边的 3.元素可取值[-1000,1000] 4.数组长度可以为1 思路1: 既然有多个中间索引时,取最左边的,那么就从最右边开始计算,如果有中间索引,覆盖上一个中间索引 直到最左边一个计算完成,返回最终的中间索引。 func pivotIndex(nums []int) int { lens := len(nums) // 起始游标 centIndex := lens-1 // 游标两侧元素的和 var leftCount , rightCount int // 初始化总值 for k, v := range nums{ if k < centIndex{ leftCount += v } if k > centIndex{ rightCount += v } } // 记录中间索引 var leftCentIndex = -1 for { if leftCount == rightCount { leftCentIndex = centIndex } // 游标从右往左 centIndex -= 1 // 结束循环 if centIndex < 0 { if -1 != leftCentIndex { return leftCentIndex } return leftCentIndex } // 游标左移,重新计算左右两边和 leftCount -= nums[centIndex] rightCount += nums[centIndex+1] } } 思路2: 思路1相反,从最左边开始,第一个相等的索引即使中间索引 func pivotIndex(nums []int) int { lens := len(nums) // 起始游标 centIndex := 0 // 游标两侧元素的和 var leftCount , rightCount int // 初始化总值 for k, v := range nums{ if k < centIndex{ leftCount += v } if k > centIndex{ rightCount += v } } // 记录中间索引 var leftCentIndex = -1 for { if leftCount == rightCount { return centIndex } // 游标从左往右 centIndex += 1 if centIndex == lens { return leftCentIndex } // 游标右移,重新计算左右两边和 leftCount += nums[centIndex-1] rightCount -= nums[centIndex] } } 疑问: 你会发现初始化right,left, 代码相对复杂,能否通过一个值来获取呢? func pivotIndex(nums []int) int{ var sum int // 初始化总和 for _,v := range nums { sum += v } var leftCount, rightCount int for k,v := range nums { // 游标默认从左边第一个开始, 减去游标对应值,再减去left总和就是right总和 rightCount = sum - leftCount - v if rightCount == leftCount{ return k } // leftCount的总值,下一次循环游标由k变为k+1了,所以此处加 v leftCount += v } return -1 }

抛砖引玉:如果还有其他更好的写法,评论码。



热门排行