2401. 最长优雅子数组 - 力扣(LeetCode)来源于题解,有自己的解读
class Solution { public: int longestNiceSubarray(vector<int>& nums) { //滑动窗口去做 int ans=0,left=0,or_=0;//or_保存最优子序列中所有数据的二进制位为1的最终组合 //right去遍历数组 for(int right=0;right<nums.size();right++) { //&后不为0,去掉左边界(异或:相同抵消) while(or_&nums[right])//用while而不是if:固定当前右边界,从左到右依次去看应该把最优子数组里面的哪些元素去掉 { or_^=nums[left++]; } //&后为0,把nums[right]加入or_中 or_|=nums[right]; ans=max(ans,right-left+1); } return ans; } };1、考察:滑动窗口 + 位运算
2、这段代码用滑动窗口(双指针)维护一个「始终满足优美条件」的窗口[left, right],并用一个变量or_记录窗口内所有数的「二进制 1 的集合」(or_的某一位为 1,说明窗口内有数字的这一位是 1)。
| 操作 | 含义 | 举例 | |
or_ & nums[right] | 判断 nums [right] 和窗口内的数是否有重叠的 1:- 结果≠0 → 有重叠(窗口不满足优美条件);- 结果 = 0 → 无重叠(可以加入窗口) | 假设 or_=011(窗口内有 1、2),nums [right]=4(100):011 & 100 = 0 → 无重叠;若 nums [right]=2(010):011 & 010 = 010≠0 → 有重叠 | |
| `or_ | = nums[right]` | 把 nums [right] 的 1 加入 or_(标记窗口内新增的 1 的位置) | or_=011,nums[right]=4(100):011 | 100 = 111 → or_更新为 111 |
or_ ^= nums[left] | 从 or_中移除 nums [left] 的 1(窗口左边界收缩,去掉该数的 1) | 前提:窗口内每个数的 1 都是唯一的(否则不能用异或),比如 or_=111,nums [left]=2(010):111 ^ 010 = 101 → or_去掉了 010 这一位 |
完整执行示例(nums = [1,3,8,48,10])
3、核心操作重用:高(&/|/^ 是位运算的基础,面试常考):
x & 1:判断奇偶;x ^ x = 0:找唯一数;x | y:合并状态;x & (x-1):消除最后一个 1(比如统计 1 的个数)。
4、总结
(1)代码核心:滑动窗口维护优美子数组,or_记录窗口内 1 的集合,用 & 判断重叠、| 添加、^ 移除;
(2)位运算关键:or_ & nums[right]≠0说明有重叠,需收缩左边界;