What is the main trick in Ways to Make a Fair Array?

The main trick is that removing index i changes the parity of every element to its right. That means you cannot just subtract nums[i] from the original even or odd sum; you must also swap how the suffix contributes to the final even and odd totals.

Why is prefix sum the right pattern for this problem?

This problem fits Array plus Prefix Sum because you need fast access to parity sums on both sides of each index. Prefix-style running totals let you test every removal in O(1) after O(1) updates, instead of recomputing sums for rebuilt arrays.

Can I solve Ways to Make a Fair Array with actual prefix arrays?

Yes. You can build prefixEven and prefixOdd arrays, then derive left and right parity sums for each removal. That is still O(n) time, but it uses O(n) extra space, while the running-sum version compresses the same idea into O(1) space.

Why does nums = [2,1,6,4] return 1?

Only removing index 1 works. The remaining array becomes [2,6,4], where even-index sum is 2 + 4 = 6 and odd-index sum is 6, so the array is fair. No other removal produces equal parity sums.

What update order should I use in the one-pass solution?

First remove nums[i] from the correct right-side bucket, then test fairness using leftEven + rightOdd and leftOdd + rightEven, and only after that add nums[i] to the left-side bucket. This order ensures the current index is treated as deleted instead of still present.

#1664

Medium

auto_awesome前缀和

LeetCode 题解工作台

生成平衡数组的方案数

给你一个整数数组 nums 。你需要选择恰好一个下标（下标从 0 开始）并删除对应的元素。请注意剩下元素的下标可能会因为删除操作而发生改变。比方说，如果 nums = [6,1,7,4,1] ，那么：选择删除下标 1 ，剩下的数组为 nums = [6,7,4,1] 。选择删除下标 2 ，…

数组前缀和

题目描述

给你一个整数数组 nums 。你需要选择恰好一个下标（下标从 0 开始）并删除对应的元素。请注意剩下元素的下标可能会因为删除操作而发生改变。

比方说，如果 nums = [6,1,7,4,1] ，那么：

选择删除下标 1 ，剩下的数组为 nums = [6,7,4,1] 。
选择删除下标 2 ，剩下的数组为 nums = [6,1,4,1] 。
选择删除下标 4 ，剩下的数组为 nums = [6,1,7,4] 。

如果一个数组满足奇数下标元素的和与偶数下标元素的和相等，该数组就是一个 平衡数组 。

请你返回删除操作后，剩下的数组 nums 是 平衡数组 的 方案数 。

示例 1：

输入：nums = [2,1,6,4]
输出：1
解释：
删除下标 0 ：[1,6,4] -> 偶数元素下标为：1 + 4 = 5 。奇数元素下标为：6 。不平衡。
删除下标 1 ：[2,6,4] -> 偶数元素下标为：2 + 4 = 6 。奇数元素下标为：6 。平衡。
删除下标 2 ：[2,1,4] -> 偶数元素下标为：2 + 4 = 6 。奇数元素下标为：1 。不平衡。
删除下标 3 ：[2,1,6] -> 偶数元素下标为：2 + 6 = 8 。奇数元素下标为：1 。不平衡。
只有一种让剩余数组成为平衡数组的方案。

示例 2：

输入：nums = [1,1,1]
输出：3
解释：你可以删除任意元素，剩余数组都是平衡数组。

示例 3：

输入：nums = [1,2,3]
输出：0
解释：不管删除哪个元素，剩下数组都不是平衡数组。

提示：

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁴

lightbulb

解题思路

方法一：枚举 + 前缀和

我们先预处理得到数组 nums 的偶数下标元素之和 $s_1$ 以及奇数下标元素之和 $s_2$ 。

然后从前往后枚举数组 nums 的每个元素 $v$ ，用变量 $t_1$ 和 $t_2$ 分别记录已遍历的偶数下标元素之和以及奇数下标元素之和。

我们观察发现，对于当前遍历到的元素 $v$ ，如果删除了，那么该元素之后的奇偶下标元素之和会发生交换。此时，我们先判断该位置下标 $i$ 是奇数还是偶数。

如果是偶数下标，删除该元素后，数组的奇数下标元素之和为 $t_2 + s_1 - t_1 - v$ ，而偶数下标元素之和为 $t_1 + s_2 - t_2$ ，如果这两个和相等，那么就是一个平衡数组，答案加一。
如果是奇数下标，删除该元素后，数组的偶数下标元素之和为 $t_1 + s_2 - t_2 - v$ ，而奇数下标元素之和为 $t_2 + s_1 - t_1$ ，如果这两个和相等，那么就是一个平衡数组，答案加一。

然后我们更新 $t_1$ 和 $t_2$ ，继续遍历下一个元素。遍历完数组后，即可得到答案。

时间复杂度 $O(n)$ ，其中 $n$ 为数组的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def waysToMakeFair(self, nums: List[int]) -> int:
        s1, s2 = sum(nums[::2]), sum(nums[1::2])
        ans = t1 = t2 = 0
        for i, v in enumerate(nums):
            ans += i % 2 == 0 and t2 + s1 - t1 - v == t1 + s2 - t2
            ans += i % 2 == 1 and t2 + s1 - t1 == t1 + s2 - t2 - v
            t1 += v if i % 2 == 0 else 0
            t2 += v if i % 2 == 1 else 0
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
They mention that indices after the removed element shift, which is a direct hint that right-side parity flips.
question_mark
They ask for something faster than rebuilding the array for every index, pushing you away from O(n^2) simulation.
question_mark
They emphasize Array and Prefix Sum topics, signaling parity-based running totals instead of deletion mechanics.

warning

常见陷阱

外企场景

error
Forgetting that only the suffix after the removed index changes parity; the prefix keeps the same even or odd positions.
error
Checking original even and odd sums after subtracting nums[i] without swapping the right-side parity contribution.
error
Updating left-side sums before testing the current removal, which makes nums[i] incorrectly remain in the kept array.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return the list of removable indices instead of the count; the same parity-sum check still works.
arrow_right_alt
Allow multiple fairness queries after point updates to nums; this pushes the problem toward segment trees or Fenwick trees with parity-aware logic.
arrow_right_alt
Ask whether removing one element can make even and odd sums differ by a target value k instead of zero; the parity-flip formula changes only in the final comparison.

help

常见问题

外企场景

继续练习

#1658 将 x 减到 0 的最小操作数 #1674 使数组互补的最少操作次数 #1685 有序数组中差绝对值之和