题目描述

给你一个整数数组 nums。你需要恰好移除一个元素后，使得剩余元素中，奇数下标元素之和等于偶数下标元素之和。返回满足条件的移除方案数。

例如：nums = [2,1,6,4]，输出 1。

解释：

  • 移除下标 0：[1,6,4]，偶数下标和 = 1+4=5，奇数下标和 = 6，5 ≠ 6
  • 移除下标 1：[2,6,4]，偶数下标和 = 2+4=6，奇数下标和 = 6，6 = 6 ✓
  • 移除下标 2：[2,1,4]，偶数下标和 = 2+4=6，奇数下标和 = 1，6 ≠ 1
  • 移除下标 3：[2,1,6]，偶数下标和 = 2+6=8，奇数下标和 = 1，8 ≠ 1
    只有移除下标 1 满足条件。

解题思路

核心思想

直接枚举每个元素被移除的情况需要 O(n²)。我们可以用前缀和的思想在 O(n) 时间内解决。

当移除下标 i 的元素后，剩余元素的下标会发生变化：

  • i 之前的元素，其下标奇偶性不变。
  • i 之后的元素，其下标奇偶性反转（原来的偶数变奇数，奇数变偶数）。

因此，移除 i 之后：

  • 新的偶数下标和 = i 之前的偶数下标和 + i 之后的奇数下标和
  • 新的奇数下标和 = i 之前的奇数下标和 + i 之后的偶数下标和（注意减去被移除的 nums[i]，如果 i 是偶数，则从偶数和中减去；如果 i 是奇数，则从奇数和中减去）

步骤

  1. 先统计整个数组的偶数下标总和 evenTotal 和奇数下标总和 oddTotal。
  2. 遍历数组，维护 evenPrefix（当前元素之前的偶数下标前缀和）和 oddPrefix（当前元素之前的奇数下标前缀和）。
  3. 对于每个下标 i，分两种情况进行计算：
    • 如果 i 是偶数下标：
      • 移除后偶数下标和 = evenPrefix + （i 之后的奇数下标总和）= evenPrefix + (oddTotal - oddPrefix)
      • 移除后奇数下标和 = oddPrefix + （i 之后的偶数下标总和）- nums[i] = oddPrefix + (evenTotal - evenPrefix - nums[i])
    • 如果 i 是奇数下标：
      • 移除后偶数下标和 = evenPrefix + （i 之后的奇数下标总和）- nums[i] = evenPrefix + (oddTotal - oddPrefix - nums[i])
      • 移除后奇数下标和 = oddPrefix + （i 之后的偶数下标总和）= oddPrefix + (evenTotal - evenPrefix)
  4. 如果移除后的偶数下标和 == 奇数下标和，ans++。
  5. 更新 evenPrefix 或 oddPrefix（根据 i 的奇偶性）。

示例说明

以 nums = [2,1,6,4] 为例：

  • evenTotal = nums[0] + nums[2] = 2 + 6 = 8
  • oddTotal = nums[1] + nums[3] = 1 + 4 = 5
  • i=0（偶数）：新偶 = 0+(5-0) = 5，新奇 = 0+(8-0-2) = 6，5≠6；更新 evenPrefix = 2
  • i=1（奇数）：新偶 = 2+(5-0-1) = 6，新奇 = 0+(8-2) = 6，6=6 ✓，ans=1；更新 oddPrefix = 1
  • i=2（偶数）：新偶 = 2+(5-1) = 6，新奇 = 1+(8-2-6) = 1，6≠1；更新 evenPrefix = 8
  • i=3（奇数）：新偶 = 8+(5-1-4) = 8，新奇 = 1+(8-8) = 1，8≠1；更新 oddPrefix = 5
  • 返回 1

复杂度分析

  • 时间复杂度：O(n)，两次遍历数组。
  • 空间复杂度：O(1)，只使用常数额外空间。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
package code.J1664;

public class J1664 {
    public int waysToMakeFair(int[] nums) {
        int n = nums.length;
        int oddTotal = 0, evenTotal = 0;
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) evenTotal += nums[i];
            else oddTotal += nums[i];
        }
        int ans = 0;
        int oddPrefix = 0, evenPrefix = 0;
        for (int i = 0; i < n; i++) {
            int currentEvenSum, currentOddSum;
            if (i % 2 == 0) {
                currentEvenSum = evenPrefix + (oddTotal - oddPrefix);
                currentOddSum = oddPrefix + (evenTotal - evenPrefix - nums[i]);
            } else {
                currentEvenSum = evenPrefix + (oddTotal - oddPrefix - nums[i]);
                currentOddSum = oddPrefix + (evenTotal - evenPrefix);
            }
            if (currentEvenSum == currentOddSum) ans++;
            if (i % 2 == 0) evenPrefix += nums[i];
            else oddPrefix += nums[i];
        }
        return ans;
    }
}