[LeetCode] 3152. Special Array II

An array is considered special if every pair of its adjacent elements contains two numbers with different parity.

You are given an array of integer nums and a 2D integer matrix queries, where for queries[i] = [fromi, toi] your task is to check that subarray nums[fromi..toi] is special or not.

Return an array of booleans answer such that answer[i] is true if nums[fromi..toi] is special.

Example 1:
Input: nums = [3,4,1,2,6], queries = [[0,4]]
Output: [false]

Explanation:
The subarray is [3,4,1,2,6]. 2 and 6 are both even.

Example 2:
Input: nums = [4,3,1,6], queries = [[0,2],[2,3]]
Output: [false,true]

Explanation:
The subarray is [4,3,1]. 3 and 1 are both odd. So the answer to this query is false.
The subarray is [1,6]. There is only one pair: (1,6) and it contains numbers with different parity. So the answer to this query is true.

Constraints:
1 <= nums.length <= 105
1 <= nums[i] <= 105
1 <= queries.length <= 105
queries[i].length == 2
0 <= queries[i][0] <= queries[i][1] <= nums.length - 1

特殊数组 II。

如果数组的每一对相邻元素都是两个奇偶性不同的数字，则该数组被认为是一个 特殊数组 。

你有一个整数数组 nums 和一个二维整数矩阵 queries，对于 queries[i] = [fromi, toi]，请你帮助你检查子数组 nums[fromi..toi] 是不是一个 特殊数组 。

返回布尔数组 answer，如果 nums[fromi..toi] 是特殊数组，则 answer[i] 为 true ，否则，answer[i] 为 false 。

思路

思路是前缀和。题目要我们判断的不是子数组的值，而是子数组内是否存在特殊数组。特殊数组的定义是如果子数组内每一对相邻元素都是两个奇偶性不同的数字，则该数组被认为是一个特殊数组。这道题利用前缀和的方式很巧妙，我们创建一个与 input 数组等长的前缀和数组，从 index = 1 那个数字开始，如果当前数字 nums[i - 1] 和 nums[i] 奇偶性不同，则 presum[i] = presum[i - 1] + 1，否则 presum[i] = presum[i - 1]。这里 + 1 的用意是当我们用前缀和去看某一段子数组的值的时候，如果这一段子数组的值大于 0，则说明这一段里肯定有奇偶性不同的数字出现；如果这一段子数组的值 == 0，则说明这一段里没有奇偶性不同的数字出现。

复杂度

时间O(n)
空间O(n)

代码

Java实现

class Solution {
    public boolean[] isArraySpecial(int[] nums, int[][] queries) {
        int n = nums.length;
        int[] presum = new int[n];
        for (int i = 1; i < n; i++) {
            presum[i] = presum[i - 1];
            if (helper(nums[i], nums[i - 1])) {
                presum[i]++;
            }
        }

        boolean[] res = new boolean[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int left = queries[i][0];
            int right = queries[i][1];
            res[i] = presum[left] == presum[right];
        }
        return res;
    }

    private boolean helper(int a, int b) {
        return a % 2 == b % 2;
    }
}