@ninijiaLeetcode每日一题练习 ------ 3097. 或值至少为 K 的最短子数组 II 中发帖

从Leetcode 每日一题练习继续讨论: 
3097. 或值至少为 K 的最短子数组 II
3097. Shortest Subarray With OR at Least K II
题解
按位或运算的结果大于等于参与运算的数字,故可以使用滑动窗口,窗口扩大的终止条件为当前窗口内所有数字的按位或大于等于k。问题在于,如何缩小窗口,缩小窗口的终止条件是什么。
考虑对窗口左侧的数字,在我们只有整个窗口的按位或的结果和该数字的情况下,无法判断缺少该数字后新窗口的按位或的结果和原始窗口的按位或结果之间的关系,因为或运算对每个二进制位只要有一个数字为1最终结果中这个二进制位就为1,因此可以同时保存窗口内各个二进制位上出现1的次数,在缩小窗口时,对移出窗口的数字中所有为1的二进制位,从保存的次数中减1,若减1后该二进制位在该窗口中出现次数为0,则从或运算结果中减去该二进制位为1,其余位置为0对...