题目

2401. 最长优雅子数组

解题思路

滑动窗口思想

1. 扩大窗口：当新来的数与窗口内的数按位与运算都为0，则加入，扩大窗口，更新答案。
2. 缩小窗口：如果新来的数与窗口内某个元素按位与运算不为0，则缩小窗口，直到新来的数与窗口内的数按位与运算都为0，再加入该数。

位运算

如何判断新来的数与窗口内的数按位与运算都为0？
暴力方法是循环窗口内的数一一比较，这样方法效率较低，可以考虑位运算。
使用一个int类型sum

1. 加入一个数c就是 sum |= c
2. 判断新来的数与窗口内的数按位与运算是否都为0就是 (sum & c) == 0
3. 缩小窗口，移除一个数d就是 sum -= d

代码

class Solution {
    public int longestNiceSubarray(int[] nums) {
        // res保存结果
        int res = 0;
        // sum记录每位1的情况
        int sum = 0;
        // 滑动窗口左右指针
        int left = 0, right = 0;
        while(right < nums.length){
            int c = nums[right];
            right++;
            if((sum & c) == 0){  //新来的数与窗口内的数按位与运算都为0, 扩大窗口
                sum |= c;  // 加入一个数c
                res = Math.max(res, right - left);  //更新答案
            }else{  // 缩小窗口
                while(left < right && (sum & c) != 0){
                    int d = nums[left];
                    left++;
                    sum -= d;  // 移除一个数
                }
                sum |= c;  // 再加入该数
            }
        }
        return res;
    }
}