leetcode 3097. 或值至少为 K 的最短子数组 II 中等

给你一个 非负 整数数组 nums 和一个整数 k 。

如果一个数组中所有元素的按位或运算 OR 的值 至少 为 k ，那么我们称这个数组是 特别的 。

请你返回 nums 中 最短特别非空 

的长度，如果特别子数组不存在，那么返回 -1 。

 

示例 1：

示例 2：

示例 3：

 

提示：

• 1 <= nums.length <= 2 * 10^5
• 0 <= nums[i] <= 10^9
• 0 <= k <= 10^9

分析：使用滑动窗口，初始时左边界L=0。遍历整个nums数组，用number记录当前进行OR运算的结果，并把所有的数字转成二进制，存储在数组里记录对应二进制位出现了几次。当number大于等于K时，从L开始减去nums[l]的对应二进制位。当某个二进制位出现次数为0时，才减去对应的2的x次方。这样从L开始一直到当前的位置i为止，继续遍历完整个数组。

int minimumSubarrayLength(int* nums, int numsSize, int k) {
    int sum[30]={0};//sum记录当前子数组所有数字的二进制位数量
    int temp=k,l=0,ans=-1,number=0;

    for(int i=0;i<numsSize;++i)
    {
        if(nums[i]>=k)return 1;//如果有一个数大于等于K，则这一个数就够了

        temp=nums[i];number=number|nums[i];//计算OR值
        for(int j=0;j<30&&temp;++j)//把当前位置的二进制组成记录下来
        {
            if(temp&1)sum[j]++;
            temp=temp>>1;
        }
        if(number>=k)//如果当前的子数组OR的和已经大于等于K，则从L开始消去
        {
            ans=ans==-1?i-l+1:fmin(ans,i-l+1);
            for(;l<=i;)
            {
                temp=nums[l];
                int xx=1;
                for(int k=0;k<30&&temp;++k)
                {
                    if(temp&1)
                    {
                        sum[k]--;
                        if(sum[k]==0)number-=xx;
                    }
                    temp=temp>>1;xx=xx<<1;
                }
                l++;
                if(number<k)break;
            }
            ans=fmin(ans,i-l+2);
        }
    }
    return ans;
}

原文地址：https://blog.csdn.net/2401_88085478/article/details/145209105

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！