Medium

题目描述

如果数组中每对相邻元素都由不同奇偶性的数字组成，则认为该数组是特殊的。

给你一个整数数组 nums 和一个二维整数矩阵 queries，其中 queries[i] = [fromi, toi]，你的任务是检查子数组 nums[fromi..toi] 是否特殊。

返回布尔数组 answer，其中 answer[i] 为 true 表示 nums[fromi..toi] 是特殊的。

示例 1：

输入：nums = [3,4,1,2,6], queries = [[0,4]]

输出：[false]

解释：

子数组是 [3,4,1,2,6]。2 和 6 都是偶数。

示例 2：

输入：nums = [4,3,1,6], queries = [[0,2],[2,3]]

输出：[false,true]

解释：

  • 子数组是 [4,3,1]。3 和 1 都是奇数。所以这个查询的答案是 false。
  • 子数组是 [1,6]。只有一对：(1,6)，它包含不同奇偶性的数字。所以这个查询的答案是 true。

约束：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5
  • 1 <= queries.length <= 10^5
  • queries[i].length == 2
  • 0 <= queries[i][0] <= queries[i][1] <= nums.length - 1

解题思路

这道题的核心是快速判断子数组中所有相邻元素是否具有不同的奇偶性。

方法一：暴力解法 对于每个查询直接遍历子数组检查相邻元素的奇偶性，时间复杂度为 O(n×m)，在约束条件下会超时。

方法二：前缀和优化（推荐） 预处理阶段：

  1. 遍历数组，记录每个位置是否与前一个位置的元素奇偶性不同
  2. 构建前缀和数组，记录从开始到当前位置有多少对相邻元素奇偶性相同

查询阶段： 对于查询 [from, to]，如果区间内所有相邻元素都奇偶性不同，则该区间特殊。通过前缀和可以 O(1) 时间判断。

方法三：分组法 将数组划分为多个连续的特殊子数组，对于每个查询检查起始和结束位置是否在同一个特殊子数组中。

前缀和方法实现简单且高效，是最优解法。

代码实现

class Solution {
public:
    vector<bool> isArraySpecial(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();
        vector<int> prefix(n, 0);
        
        // 构建前缀和数组，记录相邻元素奇偶性相同的位置数量
        for (int i = 1; i < n; i++) {
            prefix[i] = prefix[i-1];
            if ((nums[i] % 2) == (nums[i-1] % 2)) {
                prefix[i]++;
            }
        }
        
        vector<bool> result;
        for (auto& query : queries) {
            int from = query[0], to = query[1];
            // 如果区间内没有相邻元素奇偶性相同，则为特殊数组
            bool isSpecial = (prefix[to] - prefix[from] == 0);
            result.push_back(isSpecial);
        }
        
        return result;
    }
};

class Solution:
    def isArraySpecial(self, nums: List[int], queries: List[List[int]]) -> List[bool]:
        n = len(nums)
        prefix = [0] * n
        
        # 构建前缀和数组，记录相邻元素奇偶性相同的位置数量
        for i in range(1, n):
            prefix[i] = prefix[i-1]
            if (nums[i] % 2) == (nums[i-1] % 2):
                prefix[i] += 1
        
        result = []
        for from_idx, to_idx in queries:
            # 如果区间内没有相邻元素奇偶性相同，则为特殊数组
            is_special = (prefix[to_idx] - prefix[from_idx] == 0)
            result.append(is_special)
        
        return result

public class Solution {
    public bool[] IsArraySpecial(int[] nums, int[][] queries) {
        int n = nums.Length;
        int[] prefix = new int[n];
        
        // 构建前缀和数组，记录相邻元素奇偶性相同的位置数量
        for (int i = 1; i < n; i++) {
            prefix[i] = prefix[i-1];
            if ((nums[i] % 2) == (nums[i-1] % 2)) {
                prefix[i]++;
            }
        }
        
        bool[] result = new bool[queries.Length];
        for (int i = 0; i < queries.Length; i++) {
            int from = queries[i][0], to = queries[i][1];
            // 如果区间内没有相邻元素奇偶性相同，则为特殊数组
            result[i] = (prefix[to] - prefix[from] == 0);
        }
        
        return result;
    }
}

var isArraySpecial = function(nums, queries) {
    const n = nums.length;
    const prefix = new Array(n).fill(0);
    
    for (let i = 1; i < n; i++) {
        prefix[i] = prefix[i - 1];
        if (nums[i] % 2 === nums[i - 1] % 2) {
            prefix[i]++;
        }
    }
    
    const result = [];
    for (const [from, to] of queries) {
        const violations = prefix[to] - prefix[from];
        result.push(violations === 0);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度前缀和方法
时间复杂度O(n + m)，其中 n 为数组长度，m 为查询数量
空间复杂度O(n)，用于存储前缀和数组