Medium

题目描述

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

如果 nums 的子数组中位于 不同 位置的每对元素的按位 与 运算的结果等于 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

解题思路

这道题的关键在于理解"优美子数组"的定义：子数组中任意两个不同位置的元素进行按位与运算的结果都为0。

核心观察：

  1. 如果两个数的按位与结果为0，说明它们没有任何相同的二进制位为1
  2. 由于数字最大为10^9，最多需要30个二进制位，所以优美子数组的最大长度不会超过30

滑动窗口解法： 使用滑动窗口来维护一个优美子数组。关键是如何快速判断新加入的元素是否与窗口内所有元素都满足按位与为0的条件。

我们可以维护一个变量mask，表示当前窗口内所有元素按位或的结果。当要加入新元素nums[right]时：

  • 如果mask & nums[right] == 0，说明新元素与窗口内所有元素都不冲突，可以加入
  • 否则需要从左边缩小窗口，直到能够加入新元素

具体步骤：

  1. 使用双指针left和right维护滑动窗口
  2. mask记录当前窗口内所有元素的按位或结果
  3. 当mask & nums[right] != 0时，说明有冲突，需要移动左指针
  4. 移动左指针时，需要从mask中去除nums[left]的贡献
  5. 更新最大长度

时间复杂度为O(n)，因为每个元素最多被访问两次。

代码实现

class Solution {
public:
    int longestNiceSubarray(vector<int>& nums) {
        int n = nums.size();
        int left = 0, mask = 0, maxLen = 0;
        
        for (int right = 0; right < n; right++) {
            while ((mask & nums[right]) != 0) {
                mask ^= nums[left];
                left++;
            }
            mask |= nums[right];
            maxLen = max(maxLen, right - left + 1);
        }
        
        return maxLen;
    }
};

class Solution:
    def longestNiceSubarray(self, nums: List[int]) -> int:
        left = mask = max_len = 0
        
        for right in range(len(nums)):
            while mask & nums[right]:
                mask ^= nums[left]
                left += 1
            mask |= nums[right]
            max_len = max(max_len, right - left + 1)
        
        return max_len

public class Solution {
    public int LongestNiceSubarray(int[] nums) {
        int left = 0, mask = 0, maxLen = 0;
        
        for (int right = 0; right < nums.Length; right++) {
            while ((mask & nums[right]) != 0) {
                mask ^= nums[left];
                left++;
            }
            mask |= nums[right];
            maxLen = Math.Max(maxLen, right - left + 1);
        }
        
        return maxLen;
    }
}

var longestNiceSubarray = function(nums) {
    let left = 0, mask = 0, maxLen = 0;

    for (let right = 0; right < nums.length; right++) {
        while ((mask & nums[right]) !== 0) {
            mask ^= nums[left];
            left++;
        }
        mask |= nums[right];
        maxLen = Math.max(maxLen, right - left + 1);
    }

    return maxLen;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度滑动窗口解法
时间复杂度O(n)
空间复杂度O(1)

说明：

  • 时间复杂度：每个元素最多被左指针和右指针各访问一次，所以是O(n)
  • 空间复杂度：只使用了常数个额外变量

相关题目