3152. 特殊数组 II

🟠   🔖  数组 二分查找 前缀和  🔗 力扣 LeetCode

题目

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:

1. The subarray is [4,3,1]. 3 and 1 are both odd. So the answer to this query is false.
2. 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 <= 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

题目大意

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

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

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

示例 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]

解释：

1. 子数组是 [4,3,1]。3 和 1 都是奇数。因此这个查询的答案是 false。
2. 子数组是 [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

解题思路

1. 定义前缀和数组 prefix，使用变量 count 记录相邻数字奇偶性相同出现的次数；

2. 构造前缀和数组

   遍历 nums 数组，不断更新 count 和 prefix：

   • 如果 nums[i] 和 nums[i-1] 奇偶性相同，则 count += 1；
   • 将遍历到 nums[i] 时 count 的值保存到 prefix[i]；

3. 查询结果 遍历 queries 数组，对于每个查询 queries[i] = [left, right]，判断：

   • 如果 prefix[right] == prefix[left]，说明在 [left, right] 区间内，没有出现奇偶性相同的相邻数字对，返回 true；
   • 否则，返回 false；

复杂度分析

• 时间复杂度：O(n + q)，其中 n = nums.length, q = queries.length，构造 prefix 数组需要遍历 nums 一遍，查询结果需要遍历 queries 一遍。
• 空间复杂度：O(n)，用于存储 prefix 数组。

代码

/**
 * @param {number[]} nums
 * @param {number[][]} queries
 * @return {boolean[]}
 */
var isArraySpecial = function (nums, queries) {
	// 记录相邻数字奇偶性相同出现的次数
	let count = 0;

	// 构造前缀和数组
	let prefix = [0];

	for (let i = 1; i < nums.length; i++) {
		// 如果 `nums[i]` 和 `nums[i-1]` 奇偶性相同
		if (nums[i] % 2 == nums[i - 1] % 2) {
			count++;
		}
		prefix.push(count);
	}
	// 查询结果
	return queries.map(([left, right]) => prefix[right] == prefix[left]);
};