3152. 特殊数组 II

🎯 问题描述

描述：
一个数组被称为特殊数组，如果它的每一对相邻元素的奇偶性都不同（即一个是奇数，一个是偶数）。
给你一个整数数组 nums 和一个二维整数数组 queries。
对于每个查询 queries[i] = [li, ri]，你需要判断子数组 nums[li...ri] 是否是特殊数组。
返回一个布尔数组 answer，其中 answer[i] 为 true 表示该子数组是特殊的，否则为 false。

说明：

这是一个区间查询问题，核心在于判断区间内的相邻元素性质。
核心策略：
- 直接对每个查询遍历区间检查相邻元素会导致 $O(Q \cdot N)$ 的复杂度。
- 我们可以定义**“坏对”：指相邻两个元素奇偶性相同**的情况。
- 如果一个区间内“坏对”的数量为 0，则该区间是特殊的。
- 利用前缀和数组统计“坏对”的数量，实现 $O(1)$ 的查询。
示例：
示例 1：

输入：nums = [3,4,1,2,6], queries = 
输出：[false]
解释：
- 子数组 [3,4,1,2,6]
- 相邻对：
  - (3,4): 奇,偶 -> 好
  - (4,1): 偶,奇 -> 好
  - (1,2): 奇,偶 -> 好
  - (2,6): 偶,偶 -> 坏 (奇偶性相同)
- 因为存在坏对 (2,6)，所以不是特殊数组。

💻 解题思路

思路1：前缀和统计“坏对”

核心逻辑

定义“坏对”：
- 对于下标 i，如果 nums[i] 和 nums[i+1] 的奇偶性相同（即 (nums[i] & 1) == (nums[i+1] & 1)），则称 (i, i+1) 为一个“坏对”。
构建前缀和数组 pref：
- pref[i] 表示在 nums[0...i-1] 范围内（即前 i 个元素，涉及下标 0 到 i-2 的相邻对）存在的“坏对”总数。
- 注意：你的代码中 pref 的长度为 n，且 pref[i] 实际上统计的是下标 0 到 i-1 这一对是否坏（或者是累积到位置 i 的坏对数）。
- 根据你的代码逻辑：pref[i] 存储的是从下标 0 到 i-1 这一段中，以 i-1 结尾的相邻对是否为坏对的累积值。
- 递推公式：pref[i] = pref[i-1] + (1 if (nums[i-1] & 1) == (nums[i] & 1) else 0)。
处理查询：
- 对于查询 [l, r]，我们需要检查的相邻对范围是 (l, l+1) 到 (r-1, r)。
- 这些相邻对的“坏”状态被记录在 pref 数组的相应位置。
- 利用前缀和差值：pref[r] - pref[l]。
  - pref[r] 包含了直到下标 r-1 和 r 之间关系的累积（实际上你的代码逻辑中 pref 的定义略有不同，但差值逻辑是通用的）。
  - 你的代码逻辑解析：
    - pref[i] 代表 nums[0]...nums[i] 中存在的坏对数量。
    - 查询 [l, r] 涉及的对是 (l, l+1) 到 (r-1, r)。
    - 这些对的数量 = pref[r] - pref[l]。
    - 如果差值为 0，说明区间内没有坏对，返回 True。

代码实现

class Solution:
    def isArraySpecial(self, nums: List[int], queries: List[List[int]]) -> List[bool]:
        n = len(nums)
        # pref[i] 表示 nums[0...i] 范围内（即涉及下标 0 到 i-1 的相邻对）坏对的数量
        # 注意：pref[0] 默认为 0，因为没有相邻对
        pref = [0] * n
        
        # 1. 构建前缀和数组
        for i in range(1, n):
            # 检查 nums[i-1] 和 nums[i] 是否奇偶性相同
            is_bad_pair = (nums[i-1] & 1) == (nums[i] & 1)
            pref[i] = pref[i - 1] + (1 if is_bad_pair else 0)
        
        ans = []
        # 2. 处理每个查询
        for l, r in queries:
            # 区间 [l, r] 涉及的相邻对是 (l, l+1) 到 (r-1, r)
            # 这些对的数量等于 pref[r] - pref[l]
            # 解释：pref[r] 是 0...r 的坏对总数，pref[l] 是 0...l 的坏对总数
            # 相减即得到 l...r 之间的坏对数
            bad_count = pref[r] - pref[l]
            ans.append(bad_count == 0)
            
        return ans

📊 性能分析

时间复杂度： $O(N + Q)$ $O (N + Q)$
- 构建前缀和数组： $O(N)$ 。遍历一次 nums。
- 处理查询： $O(Q)$ 。每个查询只需 $O(1)$ 时间进行减法运算。
- 总体线性时间，非常高效。
空间复杂度： $O(N)$ $O (N)$
- 需要一个长度为 n 的 pref 数组。
- 结果数组 ans 占用 $O(Q)$ 空间。

思考

前缀和的定义细节：
- 你的代码中 pref[i] 实际上表示的是 nums[0] 到 nums[i] 这一段中存在的坏对数量。
- 当 i=0 时，没有相邻对，pref[0]=0。
- 当 i=1 时，检查 (0,1) 是否坏对。
- 查询 [l, r] 时，我们需要排除掉 0 到 l 之前的坏对，所以用 pref[r] - pref[l]。
奇偶性判断：
- 代码使用 (nums[i] & 1) 来判断奇偶性。
- x & 1 == 1 表示奇数，x & 1 == 0 表示偶数。
- 如果两个数奇偶性相同，它们的 & 1 结果一定相等。
为什么是 pref[r] - pref[l]？
- 区间 [l, r] 的相邻对是从索引 l 开始的（即 (l, l+1)）到索引 r-1 结束（即 (r-1, r)）。
- pref[r] 统计了直到 (r-1, r) 的所有坏对。
- pref[l] 统计了直到 (l-1, l) 的所有坏对。
- 相减正好去掉了 l 之前的部分，留下了 [l, r] 区间内的坏对。
边界情况：
- 如果 l == r，区间只有一个元素，没有相邻对，pref[r] - pref[l] = 0，返回 True，逻辑正确。