LC2401.最长优雅子数组

1. 题目

• 2401. 最长优雅子数组

给你一个由 正 整数组成的数组 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

2. 思路

• 位运算： 此题是非常标准的模板题，主要体现如下几点：
  • 如何判断元素是否在集合中 ？ x & curSet
  • 如何将元素加入集合？ x | curSet
  • 如何将元素移出集合？curSet ^= x

---

• 滑动窗口：此题也是很好的模板题
  • 先判断当前集合是否合法，如果不合法，支持将左边元素移出
  • 将右边元素加入
  • 统计最长长度

3. 代码

func longestNiceSubarray(nums []int) int {
    left, right := 0, 0
    n := len(nums)

    curAnd := 0
    ans := 0
    for right = 0; right < n; right++ {
        for left <= right && (curAnd & nums[right]) > 0 {
            curAnd = curAnd ^ nums[left]
            left++
        }

        curAnd |= nums[right]
        if right - left + 1 > ans {
            ans = right - left + 1
        }
    }

    return ans
}