3152.特殊数组II

链接：3152.特殊数组II
难度：Medium
标签：数组、二分查找、前缀和
简介：返回布尔数组 answer，如果 nums[fromi..toi] 是特殊数组，则 answer[i] 为 true ，否则，answer[i] 为 false 。

题解 1 - python

• 编辑时间：2024-08-14
• 执行用时：226ms
• 内存消耗：47.38MB
• 编程语言：python
• 解法介绍：前缀和

class Solution:
    def isArraySpecial(self, nums: List[int], queries: List[List[int]]) -> List[bool]:
        n = len(nums)
        arr = []
        i = 0
        while i < n:
            num = nums[i]
            cnt = 0
            while i + 1 < n and (nums[i + 1] ^ nums[i]) & 1:
                cnt += 1
                i += 1
            arr.append([i - cnt, i])
            i += 1
        res = []
        for q in queries:
            i = bisect_left(arr, q)
            res.append(
                i < len(arr) and q[0] >= arr[i][0] and q[1] <= arr[i][1] or \
                i - 1 >= 0 and q[0] >= arr[i - 1][0] and q[1] <= arr[i - 1][1]
            )
        return res