力扣每日一题3097

题目描述：

解析：滑动窗口解决

代码第一版：手写，超时

      int ans = Integer.MAX_VALUE;
        int left = 0;
        int currentOr = 0;
        for (int right = 0; right < nums.length; ++right) {
            currentOr |= nums[right];
            // 当前窗口内的或运算结果 >= k 时，尝试收缩窗口
            while (currentOr >= k && left <= right) {
                ans = Math.min(ans, right - left + 1);
                // 收缩窗口，left 向右移动
                left++;
                // 不能直接从 currentOr 中移除 nums[left] 的影响，
                // 重新计算 currentOr。
                currentOr = 0;
                for (int i = left; i <= right; i++) {
                    currentOr |= nums[i];
                }
            }
        }
return ans == Integer.MAX_VALUE ? -1 : ans;

第二版：官解，不是重新计算currentor，而是维护二进制位每一位中 1 出现的次数

 int n = nums.length;
    int[] bits = new int[30];
    int res = Integer.MAX_VALUE;
    for (int left = 0, right = 0; right < n; right++) {
        for (int i = 0; i < 30; i++) {
            //当窗口右边界移动时，增加右边界的第 i 位对统计的影响。
            bits[i] += (nums[right] >> i) & 1;
        }
        while (left <= right && calc(bits) >= k) {
            res = Math.min(res, right - left + 1);
            for (int i = 0; i < 30; i++) {
                //当窗口左边界移动时，减少左边界的第 i 位对统计的影响。
                bits[i] -= (nums[left] >> i) & 1;
            }
            left++;
        }
    }

    return res == Integer.MAX_VALUE ? -1 : res;
}

private static int calc(int[] bits) {
    int ans = 0;
    for (int i = 0; i < bits.length; i++) {
        if (bits[i] > 0) {
            //将 ans 的第 i 位置为 1。
            ans |= 1 << i;
        }
    }
    return ans;
}

第三版：用时最短

缺点：改变了原数组的值（但是题目问的是数组长度，无伤大雅）

int ans = Integer.MAX_VALUE;
                  for (int i = 0; i < nums.length; i++) {
                      int x = nums[i];
                      if (x >= k) {
                          return 1;
                      }
                      for (int j = i - 1; j >= 0 && (nums[j] | x) != nums[j]; j--) {
                          nums[j] |= x;
                          if (nums[j] >= k) {
                              ans = Math.min(ans, i - j + 1);
                          }
                      }
                  }
                  return ans == Integer.MAX_VALUE ? -1 : ans;
              }