LeetCode 题解工作台
分组得分最高的所有下标
给你一个下标从 0 开始的二进制数组 nums ，数组长度为 n 。 nums 可以按下标 i （ 0 ）拆分成两个数组（可能为空）： nums left 和 nums right 。 nums left 包含 nums 中从下标 0 到 i - 1 的所有元素 （包括 0 和 i - 1 ） ，而…
1
题型
6
代码语言
3
相关题
当前训练重点
中等 · 数组·driven
答案摘要
我们从 $i = 0$ 开始，用两个变量 和 分别记录 左侧和右侧的 的个数，初始时 $\textit{l0} = 0$，而 $\textit{r1} = \sum \textit{nums}$。 我们遍历数组 ，对于每个 ，更新 和 ，计算当前分组得分 $t = \textit{l0} + \textit{r1}$，如果 等于当前最大分组得分 ，则将 加入答案数组，如果 大于 ，…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·driven 题型思路
题目描述
给你一个下标从 0 开始的二进制数组 nums ，数组长度为 n 。nums 可以按下标 i（ 0 <= i <= n ）拆分成两个数组（可能为空）：numsleft 和 numsright 。
numsleft包含nums中从下标0到i - 1的所有元素（包括0和i - 1），而numsright包含nums中从下标i到n - 1的所有元素（包括i和n - 1）。- 如果
i == 0，numsleft为 空 ，而numsright将包含nums中的所有元素。 - 如果
i == n，numsleft将包含nums中的所有元素，而numsright为 空 。
下标 i 的 分组得分 为 numsleft 中 0 的个数和 numsright 中 1 的个数之 和 。
返回 分组得分 最高 的 所有不同下标 。你可以按 任意顺序 返回答案。
示例 1：
输入：nums = [0,0,1,0] 输出：[2,4] 解释：按下标分组 - 0 ：numsleft 为 [] 。numsright 为 [0,0,1,0] 。得分为 0 + 1 = 1 。 - 1 ：numsleft 为 [0] 。numsright 为 [0,1,0] 。得分为 1 + 1 = 2 。 - 2 ：numsleft 为 [0,0] 。numsright 为 [1,0] 。得分为 2 + 1 = 3 。 - 3 ：numsleft 为 [0,0,1] 。numsright 为 [0] 。得分为 2 + 0 = 2 。 - 4 ：numsleft 为 [0,0,1,0] 。numsright 为 [] 。得分为 3 + 0 = 3 。 下标 2 和 4 都可以得到最高的分组得分 3 。 注意，答案 [4,2] 也被视为正确答案。
示例 2：
输入：nums = [0,0,0] 输出：[3] 解释：按下标分组 - 0 ：numsleft 为 [] 。numsright 为 [0,0,0] 。得分为 0 + 0 = 0 。 - 1 ：numsleft 为 [0] 。numsright 为 [0,0] 。得分为 1 + 0 = 1 。 - 2 ：numsleft 为 [0,0] 。numsright 为 [0] 。得分为 2 + 0 = 2 。 - 3 ：numsleft 为 [0,0,0] 。numsright 为 [] 。得分为 3 + 0 = 3 。 只有下标 3 可以得到最高的分组得分 3 。
示例 3：
输入：nums = [1,1] 输出：[0] 解释：按下标分组 - 0 ：numsleft 为 [] 。numsright 为 [1,1] 。得分为 0 + 2 = 2 。 - 1 ：numsleft 为 [1] 。numsright 为 [1] 。得分为 0 + 1 = 1 。 - 2 ：numsleft 为 [1,1] 。numsright 为 [] 。得分为 0 + 0 = 0 。 只有下标 0 可以得到最高的分组得分 2 。
提示：
n == nums.length1 <= n <= 105nums[i]为0或1
解题思路
方法一：前缀和
我们从 开始，用两个变量 和 分别记录 左侧和右侧的 的个数，初始时 ，而 。
我们遍历数组 ，对于每个 ，更新 和 ，计算当前分组得分 ，如果 等于当前最大分组得分 ，则将 加入答案数组，如果 大于 ，则更新 为 ，并将答案数组清空，然后将 加入答案数组。
遍历结束后，返回答案数组。
时间复杂度 ，其中 为数组 的长度。空间复杂度 。
class Solution:
def maxScoreIndices(self, nums: List[int]) -> List[int]:
l0, r1 = 0, sum(nums)
mx = r1
ans = [0]
for i, x in enumerate(nums, 1):
l0 += x ^ 1
r1 -= x
t = l0 + r1
if mx == t:
ans.append(i)
elif mx < t:
mx = t
ans = [i]
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate should maintain running counts of 0's and 1's.
- question_mark
Look for clear explanation of optimizing through precomputation.
- question_mark
Expect understanding of array-driven solutions and space-time trade-offs.
常见陷阱
外企场景- error
Not maintaining running counts of 0's and 1's efficiently.
- error
Incorrect handling of boundary conditions for division (e.g., empty left or right subarrays).
- error
Failing to optimize by precomputing the right side counts.
进阶变体
外企场景- arrow_right_alt
Consider cases with very small arrays, including edge cases with 1 or 2 elements.
- arrow_right_alt
Test with large arrays near the maximum constraint to ensure performance.
- arrow_right_alt
Explore different ways of maintaining the counts (e.g., using two passes instead of one).