Leetcode 2401. Longest Nice Subarray

[Woodyiiiiiii]

此道题目的关键点：

1. subArray
2. 任意两个元素相与&为0

对于subArray，可以想到滑动窗口；但如果只用滑动窗口，当加入一个元素时，只能遍历left到right之间的所有元素，这样无疑破坏了算法的O(n)时间复杂度，这时候就要用到位运算了。

如何使用位运算，首先如果一个范围内的元素任意两个&运算为0，说明不会重复出现两个1，即1没有交集，那么要满足一个元素对范围内的所有元素&运算为0，则这个元素对于范围内所有元素的1的出现位置没有交集，所以我们可以将范围内所有元素的1收集起来，即全部｜运算，然后判断这个结果与新元素&是否为0，为0则满足，继续｜加入；否则要根据滑动窗口的思想，排出left坐标的元素，如何排除呢？可用异或^运算。

所以滑动窗口+位运算解法如下：

class Solution {
    public int longestNiceSubarray(int[] nums) {
        int res = 1;
        int temp = 0;
        int left = 0, right = 0; //[left,right]
        
        for (; right < nums.length; right++) {
            if ((temp ^ nums[right]) != (temp | nums[right])){
                res = Math.max(res, right - left);
                while ((temp ^ nums[right]) != (temp | nums[right])){
                    temp ^= nums[left++];
                }
            }
            temp |= nums[right];
        }
        
        return Math.max(res , right - left);
    }
}

时隔几个月后，我又重新写了，差不多的做法。不同的是我用一个长度为32的数组来模拟子数组的或的和。

class Solution {

    public int longestNiceSubarray(int[] nums) {
        int n = nums.length;
        int l = 0, r = 0;
        int ans = 1;
        int[] cnt = new int[32];
        while (r < n) {
            int num = nums[r];
            while (!check(num, cnt) && l < r) {
                substract(cnt, nums, l++);
            }
            plus(cnt, num);
            ans = Math.max(ans, r - l + 1);
            ++r;
        }
        return ans;
    }

    private boolean check(int num, int[] cnt) {
        for (int i = 0; i < 32; ++i) {
            if (cnt[i] > 0 && ((num >> i) & 1) != 0) {
                return false;
            }
        }
        return true;
    }

    private void substract(int[] cnt, int[] nums, int l) {
        int num = nums[l];
        for (int i = 0; i < 32; ++i) {
            if (((num >> i) & 1) == 1) {
                cnt[i]--;
            }
        }
    }

    private void plus(int[] cnt, int num) {
        for (int i = 0; i < 32; ++i) {
            if (((num >> i) & 1) == 1) {
                cnt[i]++;
            }
        }
    }

}

---

• https://leetcode.com/problems/longest-nice-subarray/