3152. 特殊数组 II

题目描述：

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

周洋哥有一个整数数组 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 <= 105
• 1 <= nums[i] <= 105
• 1 <= queries.length <= 105
• queries[i].length == 2
• 0 <= queries[i][0] <= queries[i][1] <= nums.length - 1

---

解题分析及思路：

方法：前缀和

思路：

该题为3151.特殊数组的数目的延伸题，题目要求判断子数组是否是特殊数组，即子数组的相邻元素都是奇偶性不同的数字。

由于数据量的原因，无法直接遍历整个数组，所以需要使用前缀和来记录每个位置的奇偶性不同的数字的个数。

定义一个长度为 nums.length 的数组 arraySpecialNums，其中 arraySpecialNums[i] 表示 nums[0..i] 的子数组中奇偶性不同的数字的个数。

即第一个满足特殊数组的起始位置到位置i的特殊数组元素的个数。

那么就有：

当 nums[i]%2 != nums[i-1]%2，arraySpecialNums[i] = arraySpecialNums[i-1] + 1 
当 nums[i]%2 == nums[i-1]%2，arraySpecialNums[i] = 1 

如果queries数组的子数组的起始位置和结束位置的元素个数(query[1]-query[0])与arraySpecialNums数组的起始位置和结束位置的差值(arraySpecialNums[query[1]]-arraySpecialNums[query[0]])相等，则说明则该子数组是特殊数组。

func isArraySpecial(nums []int, queries [][]int) []bool {
	var arraySpecialNums = make([]int, len(nums))
	arraySpecialNums[0] = 1
	for i := 1; i < len(nums); i++ {
		if nums[i]%2 != nums[i-1]%2 {
			arraySpecialNums[i] = arraySpecialNums[i-1] + 1
		} else {
			arraySpecialNums[i] = 1
		}
	}
	var result = make([]bool, len(queries))
	for index, query := range queries {
		result[index] = arraySpecialNums[query[1]]-arraySpecialNums[query[0]] == query[1]-query[0]
	}
	return result
}

复杂度：

• 时间复杂度：O(n)
• 空间复杂度：O(n)

执行结果：

• 执行耗时:134 ms,击败了78.17% 的Go用户
• 内存消耗:18.7 MB,击败了28.38% 的Go用户