【双指针, 位运算】最长优雅子数组

题目

6169. 最长优雅子数组

---

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

解题

方法一：双指针 位运算

思路

维护最长优雅子数组长度(maxLen)一个子数组的开始指针(start)，和结束指针(i)。

• 结束指针从数组开头向后枚举：
  • 每到一个元素再向前扫描 nums[i-1] ~ nums[start] 区间：
    • 如果与 nums[i] 做与运算都为 0 的话就说明可以把 nums[i] 加入子数组。
    • 如果到某个元素 nums[j] 与 nums[i] 做与运算不为 0 的话，说明 nums[i] 不能加入原子数组了，但是可以从 nums[j+1] 开始构造新数组(把开始指针置为 j)。
      这时如果 i - j - i > maxLen 的话就可以更新一下 maxLen。
      因为 nums[i] 也已经不能加入刚才的子数组了，再向前扫描也没有意义，可以直接 break 掉，进行下一次外层循环。

枚举完后最后一个子数组的长度还没更新，所以返回 n - start 与 maxLen 中较大的一个。

代码

class Solution {
    public int longestNiceSubarray(int[] nums) {
        int n = nums.length, start = 0, maxLen = 1;
        for (int i = 0; i < n; ++i) {
            int curr = nums[i];
            for (int j = i - 1; j >= start; --j) {
                if ((curr & nums[j]) != 0) {
                    maxLen = Math.max(maxLen, i - start);
                    start = j + 1;
                    break;
                }
            }
        }
        return Math.max(maxLen, n - start);
    }
}

class Solution {
public:
    int longestNiceSubarray(vector<int>& nums) {
        int n = nums.size(), start = 0, max_len = 1;
        for (int i = 0; i < n; ++i) {
            int curr = nums[i];
            for (int j = i - 1; j >= start; --j) {
                if (curr & nums[j]) {
                    max_len = max(max_len, i - start);
                    start = j + 1;
                    goto out;
                }
            }
            out:;
        }
        return max(max_len, n - start);
    }
};