本文涉及的基础知识点

C++算法：滑动窗口及双指针总结

LeetCode2401. 最长优雅子数组

给你一个由 正 整数组成的数组 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⁵
  1 <= nums[i] <= 10⁹

滑动窗口

性质一：如果nums[i…j]是优雅子数组，则不存在i <= i1 <i2 <=j。nums[i1]和nums[i2]相同的二进制位同时为1。
性质二：如果nums[i…j]是优雅子数组，x = nums[i…j]的或和。如果x&nums[j+1]，则nums[i…j+1]不是优雅子数组；否则，是优雅子数组。
性质三：如果nums[i…j]不是优雅数组，则$\forall$j1，j1 > j，nums[i…j1]不是优雅数组。
性质四：如果nums[i…j]是优雅数组，则nums[i1+1,j]也是优雅子数组。故i++后，j不需要复位。
移动左端点：
x ^= nums[i]
移动右端点：
x |= nums[j]

代码

核心代码

class Solution {
		public:
			int longestNiceSubarray(vector<int>& nums) {
				const int N = nums.size();
				int ans = 1,x=0;
				for (int i = 0, j = 0; i < N; i++) {
					while ((j < N) && !(x & nums[j])) {
						x |= nums[j]; j++;
					}
					ans = max(ans, j - i);
					x ^= nums[i];
				}
				return ans;
			}
		};

单元测试

vector<int> nums; 
		TEST_METHOD(TestMethod11)
		{
			nums = { 1,3,8,48,10 };
			auto res = Solution().longestNiceSubarray(nums);
			AssertEx(3, res);
		}
		TEST_METHOD(TestMethod12)
		{
			nums = { 3,1,5,11,13 };
			auto res = Solution().longestNiceSubarray(nums);
			AssertEx(1, res);
		}