Medium

题目描述

给定一个整数数组 nums，返回具有按位异或为零且包含相等数量的偶数和奇数的最长子数组的长度。如果不存在这样的子数组，则返回 0。

示例 1：

输入：nums = [3,1,3,2,0]
输出：4
解释：子数组 [1, 3, 2, 0] 的按位异或为 1 XOR 3 XOR 2 XOR 0 = 0，并且包含 2 个偶数和 2 个奇数。

示例 2：

输入：nums = [3,2,8,5,4,14,9,15]
输出：8
解释：整个数组的按位异或为 0，并且包含 4 个偶数和 4 个奇数。

示例 3：

输入：nums = [0]
输出：0
解释：没有非空子数组同时满足两个条件。

约束条件：

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^9

解题思路

这道题要求找到最长的子数组，满足两个条件：1）异或值为0；2）偶数和奇数数量相等。

核心思路： 我们需要使用前缀异或和前缀差值的思想。定义两个状态：

  • pxor：前缀异或值
  • diff：前缀偶数与奇数的数量差（偶数数量 - 奇数数量）

关键观察：

  • 如果子数组 [i+1, j] 的异或值为0，则 pxor[j] == pxor[i]
  • 如果子数组 [i+1, j] 中偶数奇数数量相等，则 diff[j] == diff[i]

因此，我们需要找到两个位置 i 和 j（j > i），使得它们的状态 (pxor, diff) 相同。

算法步骤：

  1. 遍历数组，维护前缀异或值和前缀差值
  2. 使用哈希表记录每个状态 (pxor, diff) 第一次出现的位置
  3. 当遇到相同状态时，更新最大长度

时间复杂度优化：

  • 初始状态 (0, 0) 对应索引 -1，表示空前缀
  • 每次遍历时检查当前状态是否已存在，如存在则计算子数组长度

代码实现

class Solution {
public:
    int maxBalancedSubarray(vector<int>& nums) {
        unordered_map<string, int> stateMap;
        int pxor = 0, diff = 0, maxLen = 0;
        
        // 初始状态：空前缀的状态为(0,0)，位置为-1
        stateMap["0,0"] = -1;
        
        for (int i = 0; i < nums.size(); i++) {
            pxor ^= nums[i];
            diff += (nums[i] % 2 == 0) ? 1 : -1;
            
            string state = to_string(pxor) + "," + to_string(diff);
            
            if (stateMap.find(state) != stateMap.end()) {
                maxLen = max(maxLen, i - stateMap[state]);
            } else {
                stateMap[state] = i;
            }
        }
        
        return maxLen;
    }
};

class Solution:
    def maxBalancedSubarray(self, nums: List[int]) -> int:
        state_map = {(0, 0): -1}  # 初始状态
        pxor = 0
        diff = 0
        max_len = 0
        
        for i, num in enumerate(nums):
            pxor ^= num
            diff += 1 if num % 2 == 0 else -1
            
            state = (pxor, diff)
            
            if state in state_map:
                max_len = max(max_len, i - state_map[state])
            else:
                state_map[state] = i
        
        return max_len

public class Solution {
    public int MaxBalancedSubarray(int[] nums) {
        var stateMap = new Dictionary<string, int> { ["0,0"] = -1 };
        int pxor = 0, diff = 0, maxLen = 0;
        
        for (int i = 0; i < nums.Length; i++) {
            pxor ^= nums[i];
            diff += (nums[i] % 2 == 0) ? 1 : -1;
            
            string state = $"{pxor},{diff}";
            
            if (stateMap.ContainsKey(state)) {
                maxLen = Math.Max(maxLen, i - stateMap[state]);
            } else {
                stateMap[state] = i;
            }
        }
        
        return maxLen;
    }
}

var maxBalancedSubarray = function(nums) {
    const n = nums.length;
    let maxLen = 0;
    
    // Map to store first occurrence of each (xor, balance) pair
    const map = new Map();
    map.set('0,0', -1); // base case: empty prefix
    
    let xor = 0;
    let balance = 0; // count of odd numbers - count of even numbers
    
    for (let i = 0; i < n; i++) {
        xor ^= nums[i];
        balance += (nums[i] % 2 === 1) ? 1 : -1;
        
        const key = `${xor},${balance}`;
        
        if (map.has(key)) {
            const prevIndex = map.get(key);
            const length = i - prevIndex;
            maxLen = Math.max(maxLen, length);
        } else {
            map.set(key, i);
        }
    }
    
    return maxLen;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)只需遍历数组一次，每次操作都是常数时间
空间复杂度O(n)哈希表最多存储 n 个不同的状态