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

在LeetCode上，数组中心索引问题（Find Pivot Index）是一个经典的算法问题。该问题要求我们找到一个数组的中心索引，使得该索引左侧所有元素的和等于右侧所有元素的和。本文将详细介绍如何解决这个问题，并提供相应的代码实现。

问题描述

给定一个整数数组 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
解释: 
数组中不存在满足此条件的中心索引。

解题思路

要解决这个问题，我们可以采用以下步骤：

1. 计算数组的总和：首先，我们需要计算整个数组的总和 total_sum。
2. 遍历数组：然后，我们遍历数组中的每一个元素，同时维护一个变量 left_sum，表示当前索引左侧所有元素的和。
3. 判断中心索引：对于每一个索引 i，我们可以通过 total_sum - left_sum - nums[i] 来计算右侧所有元素的和。如果 left_sum 等于右侧的和，那么当前索引 i 就是中心索引。
4. 更新左侧和：如果当前索引不是中心索引，我们将 nums[i] 加到 left_sum 中，继续遍历下一个索引。
5. 返回结果：如果遍历结束后没有找到中心索引，则返回 -1。

代码实现

以下是使用Python实现的代码：

def pivotIndex(nums):
    total_sum = sum(nums)
    left_sum = 0
    
    for i in range(len(nums)):
        if left_sum == (total_sum - left_sum - nums[i]):
            return i
        left_sum += nums[i]
    
    return -1

代码解释

• 计算总和：total_sum = sum(nums) 计算了整个数组的总和。
• 遍历数组：for i in range(len(nums)) 遍历数组中的每一个元素。
• 判断中心索引：if left_sum == (total_sum - left_sum - nums[i]) 判断当前索引是否是中心索引。
• 更新左侧和：left_sum += nums[i] 更新左侧和。
• 返回结果：如果遍历结束后没有找到中心索引，则返回 -1。

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组的长度。我们只需要遍历数组一次。
• 空间复杂度：O(1)，只使用了常数级别的额外空间。

示例运行

让我们通过一个示例来验证我们的代码。

输入: nums = [1, 7, 3, 6, 5, 6]

步骤:

1. 计算总和：total_sum = 1 + 7 + 3 + 6 + 5 + 6 = 28
2. 初始化 left_sum = 0
3. 遍历数组：
   • i = 0: left_sum = 0, 右侧和 = 28 - 0 - 1 = 27，不相等。
   • i = 1: left_sum = 1, 右侧和 = 28 - 1 - 7 = 20，不相等。
   • i = 2: left_sum = 8, 右侧和 = 28 - 8 - 3 = 17，不相等。
   • i = 3: left_sum = 11, 右侧和 = 28 - 11 - 6 = 11，相等，返回 3。

输出: 3

总结

通过上述方法，我们可以高效地找到数组的中心索引。该算法的时间复杂度为 O(n)，空间复杂度为 O(1)，非常适合处理大规模数据。希望本文能帮助你更好地理解并解决数组中心索引问题。