2401. Longest Nice Subarray

Longest Nice Subarray

題目描述：給定正整數陣列 nums，若一個子陣列中任意兩個不同元素的按位 AND（bitwise AND）為 0，稱此子陣列為「nice subarray」。求最長 nice subarray 的長度。

解題思路（位元遮罩滑動視窗）：

「任意兩個元素 AND = 0」等價於「任意兩個元素沒有共用的 bit」，亦即視窗內所有元素在 32 個 bit 位上互不衝突（每個 bit 最多被一個元素使用）。

用 usedBits 位元遮罩記錄視窗內所有元素所佔用的 bit 集合（usedBits = 視窗內所有元素的 OR）。若所有元素互不共用 bit，則 usedBits 的各位元恰好對應到唯一的某個元素。

演算法：

1. 初始化 usedBits = 0，左指針 l = 0。
2. 右指針 r 向右擴展，嘗試加入 nums[r]。
3. 若 nums[r] & usedBits != 0（有共用 bit），從左側縮小視窗：
   • usedBits ^= nums[l]（XOR 清除 nums[l] 佔用的 bit，因無共用 bit 時 XOR 等於清除）
   • l++
   • 重複直到 nums[r] & usedBits == 0。
4. 將 nums[r] 加入視窗：usedBits |= nums[r]。
5. 更新最大長度 r - l + 1。

關鍵：移除 nums[l] 時用 usedBits ^= nums[l]（等同於 usedBits &= ~nums[l]，但 XOR 在無共用 bit 的情況下更高效）。

時間複雜度：O(n) — 雙指針各最多移動 n 次，每次操作 O(1)，整體線性。

空間複雜度：O(1) — 只使用常數個整數變數（usedBits、l、ans），無需額外空間。

方法二：暴力雙重迴圈

枚舉所有子陣列 [l, r]，維護一個 usedBits 遮罩，逐一加入元素時檢查是否有共用 bit。時間 O(n²)，空間 O(1)。當 n = 10⁵ 時有 10¹⁰ 次操作，超時；適合驗證正確性。

方法三：排序 + 貪心

此問題不適合排序法，因為子陣列要求連續性（元素順序不能改變），排序後連續性被破壞。此方法不適用。

方法四：暴力位元統計

對每個子陣列統計每個 bit 位的使用次數，若所有 bit 計數均 ≤ 1 則為 nice subarray。本質與雙重迴圈相同，時間 O(n² · 32) = O(n²)，但常數更大，不推薦。

1. 若條件改為「任意兩個元素的按位 OR = 全 1（即 2³²-1）」，問題如何轉化？滑動視窗是否仍然適用？
2. 若問題改為找最長子陣列使得任意兩元素的 XOR ≥ k，有無類似的位元遮罩技巧？
3. 此題中 usedBits ^= nums[l] 能正確清除 nums[l] 的 bit，前提是視窗內沒有任何兩個元素共用 bit。若允許共用 bit（條件放鬆），該清除操作如何安全地改寫？