題目資訊

• 題目編號: 2401
• 題目連結: Longest Nice Subarray
• 主題: Array, Bit Manipulation, Sliding Window

題目敘述

您有一個由正整數組成的陣列 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 \leq nums.length \leq 10^5$
• $1 \leq nums[i] \leq 10^9$

直覺

這個問題需要找出一個最長的子陣列，使得在該子陣列中所有不同位置的元素之間的逐位元AND運算結果皆為零。這個條件保證了在所選擇的子陣列中沒有兩個數字在二進位表示中共享相同的位元。挑戰在於如何有效地管理重疊的元素以確保它們滿足此約束條件，同時最大化子陣列的長度。

由於輸入陣列的大小有很大的限制，若使用暴力方法檢查所有子陣列將會在計算上非常昂貴。因此，需要使用更有效率的滑動窗口方法來動態調整子陣列。

解法

我們使用滑動窗口方法，結合逐位元運算，以有效地確定並延伸最長的「nice」子陣列。演算法步驟如下：

1. 初始化變數： 我們首先初始化一些變數來追蹤最長的子陣列長度 (longestLength)、當前子陣列長度 (currentLength)、滑動窗口的兩個指標 (left 和 right)，以及用來存儲當前子陣列的累積逐位元AND結果的變數 (currentBitwiseAnd)。

2. 遍歷陣列： 開始以 right 指標遍歷陣列。這個指標將嘗試通過包含新元素來擴展子陣列。

3. 調整窗口： 對於 right 指標的每個位置：

   • 檢查在 right 位置包含當前元素是否保持「nice」屬性，即確保當前元素與 currentBitwiseAnd 的逐位元AND為零。
   • 若不滿足條件，則增加 left 指標，並通過去除 left 位置的元素更新 currentBitwiseAnd，直到滿足條件為止。這可以通過用 left 位置元素對 currentBitwiseAnd 進行逐位元XOR來實現，有效地把它排除在窗口之外。

4. 更新當前 AND： 確保子陣列為「nice」後，通過逐位元OR操作來更新 currentBitwiseAnd，以包含 right 元素。

5. 計算最大長度： 持續追蹤迄今為止看到的這種子陣列的最大長度，並更新 longestLength。

6. 返回結果： 遍歷陣列後，返回計算出的 longestLength，這反映了找到的「nice」子陣列的最大長度。

此方法有效地管理問題的約束條件，同時確保操作隨著輸入大小呈線性增長，因此達到了此問題所需的最佳性能。

程式碼

C++

class Solution {
public:
    // 函數用於返回最長的 nice 子陣列的長度
    int longestNiceSubarray(vector<int>& nums) {
        int longestLength = 1; // 將最長長度初始化為 1（最小 nice 子陣列）
        int currentLength = 1; // 當前子陣列長度
        int left = 0; // 滑動窗口的左指標
        int right = 0; // 滑動窗口的右指標
        int currentBitwiseAnd = 0; // 當前窗口的累積按位與
        int len = nums.size(); // 輸入陣列的大小
        
        // 使用右指標遍歷陣列
        for (; right < len; right++) {
            // 調整左指標直到當前元素可以被添加到一個 nice 子陣列
            while ((nums[right] & currentBitwiseAnd) != 0) {
                currentBitwiseAnd ^= nums[left++]; // 將左元素從當前與中排除
            }
            currentBitwiseAnd |= nums[right]; // 將當前元素包含在當前與中
            // 使用當前子陣列長度更新最長長度
            longestLength = max(longestLength, right - left + 1);
        }
        
        return longestLength; // 返回找到的 nice 子陣列的最大長度
    }
};

Python

class Solution:
    # 函數用於返回最長完美子陣列的長度
    def longestNiceSubarray(self, nums):
        longestLength = 1  # 將最長長度初始化為1（最小完美子陣列）
        left = 0  # 滑動窗口的左指標
        right = 0  # 滑動窗口的右指標
        currentBitwiseAnd = 0  # 當前窗口的累計位元AND
        len_nums = len(nums)  # 輸入陣列的大小
        
        # 使用右指標遍歷陣列
        for right in range(len_nums):
            # 調整左指標直到當前元素可以添加到完美子陣列
            while (nums[right] & currentBitwiseAnd) != 0:
                currentBitwiseAnd ^= nums[left]  # 將左側元素從當前AND中排除
                left += 1
            currentBitwiseAnd |= nums[right]  # 將當前元素包括在當前AND中
            # 使用當前子陣列的長度更新最長長度
            longestLength = max(longestLength, right - left + 1)
        
        return longestLength  # 返回找到的完美子陣列的最大長度

複雜度分析

• 時間複雜度: $O(n)$

  該演算法利用滑動視窗技術與兩個指標：left 和 right。right 指標遍歷輸入數組 nums 的每個元素，這導致了至多運行 $n$ 次的迴圈，其中 $n$ 是數組的長度。在此迴圈中，left 指標僅向前推進，不會回退，因此在最壞情況下，兩個指標在數組上合計只會移動 $n$ 步。因此，該演算法的整體時間複雜度為線性，即 $O(n)$。

• 空間複雜度: $O(1)$

  該演算法的空間複雜度是常數的，即 $O(1)$，因為該演算法使用的額外空間量不依賴於輸入數組的大小。主要的額外變量包括整數如 longestLength、currentLength、left、right、currentBitwiseAnd 和 len，它們佔用的空間是固定的。未使用其他額外的數據結構。