目标
如果数组的每一对相邻元素都是两个奇偶性不同的数字，则该数组被认为是一个 特殊数组 。
有一个整数数组 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]
解释：
子数组是 [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
思路
类似于特殊数组I，只不过是判断子数组是否是特殊数组。我们可以记录奇偶性相同的下标，如果 queries[i] = [fromi, toi] 包含其中的下标对返回false。但是如果所有元素的奇偶性都相同，下标对有n个，查询也是n次，O(n^2) 对于 10^5 的数据规模会超时。
我们可以将问题转化一下，由于仅考虑相邻元素的奇偶性，将数组中的偶数元素都替换为0，奇数元素都替换为1，这样0与1交替出现的是特殊数组。使用前缀和判断不了是否交替出现，只能初步排除一些区间。
之所以超时是因为进行了许多重复判断，我们想直接判断查询区间是否包含奇偶相同的下标对。可以使用二分查找，如果查出的from，to下标相同，说明不相交。
这里比较坑的一点是，题目中没有说明如果查询区间只包含一个值视为奇偶性不同。
log2(10^5) ≈ 16.6 时间复杂度为O(nlogn)，耗时30ms，说明10^6的数据规模，O(n)的解法不会超时，以后多留意一下。
看了题解，其实可以使用前缀和，只不过不是将原数组转为0或1计算前缀和，而是定义数组diff，原数组nums相邻元素奇偶性相同为0，不同为1。对应给定的区间，我们就可以根据diff的前缀和判断是否含有奇偶性相同的元素。时间复杂度为O(n)，耗时3ms。
也有使用动态规划求解的，记录最近一次奇偶性相同的位置。时间复杂度为O(n)，耗时3ms。
代码
/**
* @date 2024-08-14 9:58
*/
public class IsArraySpecial3152 {
public boolean[] isArraySpecial_v1(int[] nums, int[][] queries) {
int n = nums.length;
List<Integer> from = new ArrayList<>();
List<Integer> to = new ArrayList<>();
for (int i = 1; i < n; i++) {
int j = i - 1;
if (nums[i] % 2 == nums[j] % 2) {
from.add(j);
to.add(i);
}
}
int l = from.size();
int[] fromArray = new int[l];
int[] toArray = new int[l];
for (int i = 0; i < l; i++) {
fromArray[i] = from.get(i);
toArray[i] = to.get(i);
}
int length = queries.length;
boolean[] res = new boolean[length];
Arrays.fill(res, true);
for (int i = 0; i < length; i++) {
int[] query = queries[i];
if (query[0] == query[1]) {
// 如果查询区间相同认为是特殊区间
res[i] = true;
continue;
}
int fromIndex = Arrays.binarySearch(fromArray, query[0]);
if (fromIndex >= 0) {
// 如果需要查询的数组包含了query[0]，由于前面判断了相等的情况，
// 执行到这里query[1] > query[0]，而对应的toIndex 为 fromIndex + 1，
// 推出 query[1] >= toIndex，说明包含奇偶性相同的下标对，
res[i] = false;
continue;
}
int toIndex = Arrays.binarySearch(toArray, query[1]);
if (fromIndex != toIndex) {
// 执行到这里，fromIndex < 0，如果 toIndex >= 0，由于 query[0] < query[1]，推出 query[0] <= fromIndex
// 如果 toIndex < 0，说明查询区间开始与结束下标都没有找到，
// 如果插入位置不同，说明也包含了奇偶性相同的元素
res[i] = false;
}
}
return res;
}
}
性能
