What is the sliding window technique used in the Longest Nice Subarray problem?

The sliding window technique is used to maintain a dynamic subarray where elements are checked for validity using bitwise AND operations. As the window slides, invalid subarrays are removed efficiently.

How does bitwise AND help determine the validity of a subarray in this problem?

Bitwise AND ensures that no two elements in the subarray have overlapping bits. If the AND of any two elements is non-zero, the subarray is invalid.

What is the time complexity of the Longest Nice Subarray problem?

The time complexity is O(n), as the solution uses a sliding window to scan through the array once while maintaining a running AND state.

What is the maximum possible length of a nice subarray?

The maximum length depends on the array, but the sliding window approach ensures that we find the longest subarray with valid AND conditions efficiently.

How does GhostInterview help in solving this problem?

GhostInterview focuses on guiding you through efficient sliding window techniques, bitwise operations, and state management, making the solution process smoother and faster.

#2401

Medium

auto_awesome滑动窗口（状态滚动更新）

LeetCode 题解工作台

最长优雅子数组

给你一个由正整数组成的数组 nums 。如果 nums 的子数组中位于不同位置的每对元素按位与（AND）运算的结果等于 0 ，则称该子数组为优雅子数组。返回最长的优雅子数组的长度。子数组是数组中的一个连续部分。注意：长度为 1 的子数组始终视作优雅子数组。示例 …

数组位运算滑动窗口

题目描述

给你一个由正整数组成的数组 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⁵
1 <= nums[i] <= 10⁹

lightbulb

解题思路

方法一：双指针

根据题目描述，子数组的每个元素的二进制位上的 $1$ 的位置不能相同，这样才能保证任意两个元素的按位与结果为 $0$ 。

因此，我们可以使用双指针 $l$ 和 $r$ 维护一个滑动窗口，使得窗口内的元素满足题目条件。

我们用一个变量 $\textit{mask}$ 来表示窗口内的元素的按位或的结果，接下来，遍历数组的每个元素。对于当前元素 $x$ ，如果 $\textit{mask}$ 和 $x$ 的按位与结果不为 $0$ ，说明当前元素 $x$ 与窗口内的元素有重复的二进制位，此时需要移动左指针 $l$ ，直到 $\textit{mask}$ 和 $x$ 的按位与结果为 $0$ 。然后，我们将 $\textit{mask}$ 和 $x$ 的按位或的结果赋值给 $\textit{mask}$ ，并更新答案 $\textit{ans} = \max(\textit{ans}, r - l + 1)$ 。

遍历结束后，返回答案 $\textit{ans}$ 即可。

时间复杂度 $O(n)$ ，其中 $n$ 为数组 $\textit{nums}$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def longestNiceSubarray(self, nums: List[int]) -> int:
        ans = mask = l = 0
        for r, x in enumerate(nums):
            while mask & x:
                mask ^= nums[l]
                l += 1
            mask |= x
            ans = max(ans, r - l + 1)
        return ans

speed

复杂度分析

指标	值
时间	O(n)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Look for an understanding of sliding window with running state updates.
question_mark
Expect explanations of bitwise operations and their role in ensuring the subarray's validity.
question_mark
Test for clarity on maintaining the subarray's length while adjusting the window.

warning

常见陷阱

外企场景

error
Incorrect handling of subarrays with overlapping elements.
error
Misunderstanding the role of bitwise AND and not updating the state correctly.
error
Failing to shrink the window properly when a subarray becomes invalid.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Test with arrays where all elements are powers of 2.
arrow_right_alt
Handle the case where no valid subarray can be formed.
arrow_right_alt
Test with the minimum input size to check edge cases.

help

常见问题

外企场景

继续练习

#2411 按位或最大的最小子数组长度 #2932 找出强数对的最大异或值 I #2935 找出强数对的最大异或值 II