[LeetCode] 2401. Longest Nice Subarray

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 the longest 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 <= 105
1 <= nums[i] <= 109

最长优雅子数组。

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

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

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

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

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

思路

思路是滑动窗口，而且这道题涉及位运算。

题目让我们找的是一个满足题意的优雅子数组。看到子数组，不是说思路一定是滑动窗口，但是滑动窗口是一个比较好的选择，因为滑动窗口的复杂度一般在O(n)。但是这道题涉及到位运算，而且题目对优雅的定义是子数组之间每两个元素之间都要满足AND的结果为 0。那么如何定义一堆数字互相做AND操作的结果为0呢？这里我们可以用异或XOR来实现。因为异或的特性是，两个数相同为0，不同为1。如果一堆数字XOR的结果为0，说明这一堆数字里面出现的1都在32个bit的不同位置上。

• 回到题目，我们可以使用滑动窗口（双指针）来维护一个窗口，使得窗口内的所有数字按位与AND结果为零。
• 维护一个变量 or 记录窗口内所有元素的按位或（OR），用于快速检查是否满足条件：
  • 若 nums[right] & or == 0，则 nums[right] 可以加入窗口，更新 or。
  • 否则，需要移动 left 指针，直到 nums[right] 能够加入窗口。

在遍历过程中，维护 最大窗口长度 作为答案。

为什么 nums[right] 被加入窗口的时候是用 or 是因为 or 变量记录的是 32 个 bit 上出现过 1 的位置。如果 nums[right] & or == 0，说明 nums[right] 和窗口内的所有元素按位与的结果为 0，即 nums[right] 可以加入窗口。

为什么 nums[left] 从窗口被移除的时候是做 xor 操作是因为 nums[left] 被移除的时候我们需要去掉 nums[left] 对 or 贡献的所有的 1。如果 or 在某一些 bit 上是 1，那么当 or 跟 nums[left] 做 xor 的时候，这些 bit 上的 1 会被去掉。

复杂度

时间O(n)
空间O(1)

代码

Java实现

class Solution {
    public int longestNiceSubarray(int[] nums) {
        int start = 0;
        int end = 0;
        int or = 0;
        int res = 0;
        while (end < nums.length) {
            while ((or & nums[end]) != 0) {
                or ^= nums[start];
                start++;
            }
            or |= nums[end];
            end++;
            res = Math.max(res, end - start);
        }
        return res;
    }
}