2401. 最长优雅子数组

🟠   🔖  位运算 数组 滑动窗口  🔗 力扣 LeetCode

题目

You are given an array nums consisting of positive integers.

We call a subarray of nums nice if the bitwise AND of every pair of elements that are in different positions in the subarray is equal to 0.

Return the length of thelongest nice subarray.

A subarray is a contiguous part of an array.

Note that subarrays of length 1 are always considered nice.

Example 1:

Input: nums = [1,3,8,48,10]

Output: 3

Explanation: The longest nice subarray is [3,8,48]. This subarray satisfies the conditions:

• 3 AND 8 = 0.
• 3 AND 48 = 0.
• 8 AND 48 = 0.

It can be proven that no longer nice subarray can be obtained, so we return 3.

Example 2:

Input: nums = [3,1,5,11,13]

Output: 1

Explanation: The length of the longest nice subarray is 1. Any subarray of length 1 can be chosen.

Constraints:

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9

题目大意

给你一个由 正 整数组成的数组 nums 。

如果 nums 的子数组中位于 不同 位置的每对元素按位 与（AND） 运算的结果等于 0 ，则称该子数组为 优雅 子数组。

返回 最长 的优雅子数组的长度。

子数组 是数组中的一个 连续 部分。

注意： 长度为 1 的子数组始终视作优雅子数组。

示例 1：

输入： nums = [1,3,8,48,10]

输出： 3

解释： 最长的优雅子数组是 [3,8,48] 。子数组满足题目条件：

• 3 AND 8 = 0
• 3 AND 48 = 0
• 8 AND 48 = 0

可以证明不存在更长的优雅子数组，所以返回 3 。

示例 2：

输入： nums = [3,1,5,11,13]

输出： 1

解释： 最长的优雅子数组长度为 1 ，任何长度为 1 的子数组都满足题目条件。

提示：

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9

解题思路

可以使用 滑动窗口 方法维护一个合法的子数组，并使用按位运算来快速检查是否合法。

1. 使用 mask 记录窗口内所有元素的按位 OR 结果：

   • mask |= nums[r] 表示把 nums[r] 加入窗口，更新 mask。

2. 如果 nums[r] & mask != 0，说明新加入的 nums[r] 产生了冲突：

   • 通过 mask ^= nums[l] 移除 nums[l]，然后 l++ 直到窗口合法。

3. 更新最大长度：

   • maxLen = max(maxLen, r - l + 1)

复杂度分析

• 时间复杂度：O(n)，每个元素最多被加入和移除窗口一次。
• 空间复杂度：O(1)，只使用了 mask, l, maxLen 这些变量，不依赖额外的数据结构。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestNiceSubarray = function (nums) {
	let mask = 0;
	let l = 0;
	let maxLen = 0;

	for (let r = 0; r < nums.length; r++) {
		// 当 nums[r] & mask != 0 时，说明有重叠的 1，需要缩小窗口
		while ((nums[r] & mask) !== 0) {
			mask ^= nums[l]; // 移除左侧元素
			l++;
		}
		mask |= nums[r]; // 加入新元素

		maxLen = Math.max(r - l + 1, maxLen);
	}

	return maxLen;
};

相关题目

题号	标题	题解	标签	难度	力扣
3	无重复字符的最长子串	[✓]	哈希表 字符串 滑动窗口	🟠	🀄️ 🔗
201	数字范围按位与	[✓]	位运算	🟠	🀄️ 🔗
898	子数组按位或操作		位运算 数组 动态规划	🟠	🀄️ 🔗
904	水果成篮		数组 哈希表 滑动窗口	🟠	🀄️ 🔗
1004	最大连续1的个数 III	[✓]	数组 二分查找 前缀和 1+	🟠	🀄️ 🔗
1208	尽可能使字符串相等		字符串 二分查找 前缀和 1+	🟠	🀄️ 🔗
1838	最高频元素的频数		贪心 数组 二分查找 3+	🟠	🀄️ 🔗
1839	所有元音按顺序排布的最长子字符串		字符串 滑动窗口	🟠	🀄️ 🔗
2024	考试的最大困扰度		字符串 二分查找 前缀和 1+	🟠	🀄️ 🔗
2461	长度为 K 子数组中的最大和	[✓]	数组 哈希表 滑动窗口	🟠	🀄️ 🔗