leetcode:寻找数组的中心索引

简介:

正文


36.png算法:

既然需要找到这个中心的位置,那么,首先应该知道每一个位置的和是多少,这样的话,我们就可以设计出来一个数组,专门保存我们当前的累加和,方便与后续的操作。


37.png

时间复杂度:O(N)

空间复杂度:O(N)

最后的代码:


class Solution724:
    def pivotIndex(self, nums: List[int]) -> int:
        res = -1
        n = len(nums)
        if n == 0:
            return -1
        elif n == 1:
            return 0
        elif n < 3:
            return -1
        else:
            sum_list = [0 for i in range(n)]
            sum_list[0] = nums[0]
            for j in range(1, n):
                sum_list[j] = sum_list[j - 1] + nums[j]
            if sum_list[n - 1] == sum_list[0]:
                return 0
            for j in range(1, n - 1):
                if sum_list[j - 1] == sum_list[n - 1] - sum_list[j]:
                    return j
            if sum_list[n - 2] == 0:
                return n - 1
        return res

最后一定不要忘记边界值哈!!!!


相关文章
|
4月前
|
Go
【LeetCode 热题100】DP 实战进阶:最长递增子序列、乘积最大子数组、分割等和子集(力扣300 / 152/ 416 )(Go语言版)
本文深入解析三道经典的动态规划问题:**最长递增子序列(LIS)**、**乘积最大子数组** 和 **分割等和子集**。 - **300. LIS** 通过 `dp[i]` 表示以第 `i` 个元素结尾的最长递增子序列长度,支持 O(n²) 动态规划与 O(n log n) 的二分优化。 - **152. 乘积最大子数组** 利用正负数特性,同时维护最大值与最小值的状态转移方程。 - **416. 分割等和子集** 转化为 0-1 背包问题,通过布尔型 DP 实现子集和判断。 总结对比了三题的状态定义与解法技巧,并延伸至相关变种问题,助你掌握动态规划的核心思想与灵活应用!
136 1
|
12月前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
109 0
LeetCode第53题最大子数组和
LeetCode第53题"最大子数组和"的解题方法,利用动态规划思想,通过一次遍历数组,维护到当前元素为止的最大子数组和,有效避免了复杂度更高的暴力解法。
LeetCode第53题最大子数组和
|
12月前
【LeetCode-每日一题】 删除排序数组中的重复项
【LeetCode-每日一题】 删除排序数组中的重复项
82 4
|
12月前
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
94 0
Leetcode第三十三题(搜索旋转排序数组)
LeetCode第81题搜索旋转排序数组 II
文章讲解了LeetCode第81题"搜索旋转排序数组 II"的解法,通过二分查找算法并加入去重逻辑来解决在旋转且含有重复元素的数组中搜索特定值的问题。
LeetCode第81题搜索旋转排序数组 II
|
12月前
|
算法 C++
Leetcode第53题(最大子数组和)
这篇文章介绍了LeetCode第53题“最大子数组和”的动态规划解法,提供了详细的状态转移方程和C++代码实现,并讨论了其他算法如贪心、分治、改进动态规划和分块累计法。
181 0
|
12月前
|
C++
【LeetCode 12】349.两个数组的交集
【LeetCode 12】349.两个数组的交集
76 0
|
算法 索引
LeetCode第34题在排序数组中查找元素的第一个和最后一个位置
这篇文章介绍了LeetCode第34题"在排序数组中查找元素的第一个和最后一个位置"的解题方法,通过使用双指针法从数组两端向中间同时查找目标值,有效地找到了目标值的首次和最后一次出现的索引位置。
LeetCode第34题在排序数组中查找元素的第一个和最后一个位置
LeetCode第33题搜索旋转排序数组
这篇文章介绍了LeetCode第33题"搜索旋转排序数组"的解题方法,通过使用二分查找法并根据数组的有序性质调整搜索范围,实现了时间复杂度为O(log n)的高效搜索算法。
LeetCode第33题搜索旋转排序数组

热门文章

最新文章