LeetCode 补充题 130. 偶数和非空子序列计数
题目描述
给你一个整数数组
nums，请返回元素和为偶数的非空子序列数量。子序列可以不连续，但必须保持原下标的相对顺序。不同的下标选择视为不同方案。
返回精确计数，不需要取模；结果可能超过 64 位整数范围。空数组返回
0。
示例 1：
输入：
nums = [1,2,3]
输出：3
解释： 符合条件的是[2]、[1,3]、[1,2,3]。
示例 2：
输入：
nums = [0,2,4]
输出：7
解释： 所有非空下标子集的和都是偶数，共 2³−1 种。
提示：
- 允许负数和
0。 - 空数组返回
0。 - 计数可能超过
64位，Java 使用BigInteger，Go 使用big.Int。
题意分析
每一组递增下标唯一对应一个子序列，所以可以直接统计下标子集，不需要枚举其元素和。结果只受是否存在奇数影响：偶数不会改变和的奇偶性，选入一个奇数则会翻转奇偶性。
解法：切换一个奇数位置配对子集
核心思路
[!blue]
若有奇数，固定它所在的一个下标。对任意子集，将这个下标由不选改为选或由选改为不选，和的奇偶性必然翻转；再切换一次又回到原集合。因此所有子集被一一配成一奇一偶，偶数和子集共有 $2^{n-1}$ 个。
若没有奇数，所有元素都是偶数，包括负偶数和 0，全部 $2^n$ 个子集的和都为偶数。两种情况都包含唯一的空集，最后统一减 1。
Java 用
BigInteger、Go 用big.Int移位计算精确的 2 的幂，避免固定整数宽度溢出。空数组进入无奇数分支，得到2^0 - 1 = 0，不需要特殊递归处理。
解题步骤
- 扫描是否存在奇数。
- 存在奇数时，偶数和子集为全部子集的一半；否则全部子集都是偶数和。
- 用大整数计算 2 的对应次幂，最后减去空集。
代码实现
class Solution {
public BigInteger evenSubsequences(int[] nums) {
boolean odd = false;
for (int value : nums) {
if ((value & 1) != 0) {
odd = true;
break;
}
}
int exponent = nums.length - (odd ? 1 : 0);
return BigInteger.ONE.shiftLeft(exponent).subtract(BigInteger.ONE);
}
}
import "math/big"
func evenSubsequences(nums []int) *big.Int {
odd := false
for _, value := range nums {
if value&1 != 0 {
odd = true
break
}
}
exponent := len(nums)
if odd {
exponent--
}
out := new(big.Int).Lsh(big.NewInt(1), uint(exponent))
return out.Sub(out, big.NewInt(1))
}
复杂度分析
- 时间复杂度：$O(n)$。
- 空间复杂度：大整数结果占 $O(n)$ 位；除结果外只需常数个状态。
关键点总结
[!green]
固定一个奇数位置，切换选或不选就是偶数和与奇数和子集的一一配对；重复值仍对应不同下标。
易错点总结
[!yellow]
只有连续区间才适用前缀奇偶计数；本题允许不连续，应按下标子集计数。空集必须且只扣除一次。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 78. 子集 | 中等 | 每个下标选或不选形成全部子集，本题只计偶数和并扣除空集。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！