3095. 或值至少 K 的最短子数组 I
3097. 或值至少为 K 的最短子数组 II

题解

class Solution {
public:
    int minimumSubarrayLength(vector<int>& nums, int k) {
        int ans = INT_MAX;
        for (int i = 0; i < nums.size(); i++) {
            int x = nums[i];
            if (x >= k)
                return 1;
            // 窗口向前延伸，如果nums[j] | x == nums[j]
            // 说明加上这个数和不加一样，所以跳过。
            for (int j = i - 1; j >= 0 && (nums[j] | x) != nums[j]; j--) {
                nums[j] |= x;
                if (nums[j] >= k) {
                    ans = min(ans, i - j + 1);
                    break;
                }
                if (i - j + 1 >= ans - 1) // 剪枝
                    break;
            }
        }
        return ans == INT_MAX ? -1 : ans;
    }
};

思路

滑动窗口

该思路为什么适用？因为这一题有两个要求：最短、连续子数组。

从nums[i]向前遍历，并且直接对之前的数组值进行修改，将nums[j] |= nums[i]，这里也利用的位运算的特性，如果换成是累加或者是累乘都不可用。这样只需要每次向前遍历的时候判断nums[j]与k的大小，一旦nums[j]>=k就表示该子数组满足要求，这时候只需要将子数组长度与ans比较，更新最终结果为较小的值即可。

对此，剪枝策略就是，如果往前遍历时，nums[j]并不会对最终结果造成影响（即(nums[j] | x) == nums[j]，表示nums[j]加入按位或运算并不影响结果），那么就直接跳出子循环；另外，也可以对子数组长度进行剪枝，如果遍历时长度已经比ans大了，则直接跳出循环。