Leecode刷题C语言之或值至少K的最短子数组①

 执行结果:通过

执行用时和内存消耗如下：

 

int minimumSubarrayLength(int* nums, int numsSize, int k) {
    int left = 0;
    int right = 0;
    int currentOr = 0;
    int minLength = INT_MAX;

    while (right < numsSize) {
        // 扩展窗口，添加新元素到 currentOr
        currentOr |= nums[right];

        // 当 currentOr >= k 时，尝试收缩窗口
        while (currentOr >= k && left <= right) {
            // 更新最短长度
            if (right - left + 1 < minLength) {
                minLength = right - left + 1;
            }
            // 移除左端点元素，并更新 currentOr
            int tempOr = 0;
            for (int i = left + 1; i <= right; ++i) {
                tempOr |= nums[i];
            }
            currentOr = tempOr;
            ++left;
        }

        ++right;
    }

    // 检查是否有符合条件的子数组
    return minLength == INT_MAX ? -1 : minLength;
}

解题思路：

这段代码的解题思路旨在寻找一个最短的连续子数组，使得该子数组中所有数字的按位或（bitwise OR）结果大于等于给定的整数 k。以下是详细的解题步骤：

1. 初始化变量：
   • left 和 right 分别表示当前考虑的子数组的左右边界，初始都设为 0。
   • currentOr 用于存储当前子数组内所有元素的按位或结果，初始化为 0。
   • minLength 用于记录符合条件的最短子数组的长度，初始化为 INT_MAX（一个非常大的数，表示初始时未找到符合条件的子数组）。
2. 遍历数组：
   • 使用一个 while 循环遍历数组，条件是 right < numsSize，即右边界未超出数组长度。
3. 扩展窗口：
   • 在每次循环中，首先通过 currentOr |= nums[right] 将当前元素加入到 currentOr 中，扩展窗口的右边界。
4. 尝试收缩窗口：
   • 检查 currentOr 是否大于等于 k。如果是，说明当前窗口（或更大的窗口）可能包含符合条件的子数组。
   • 进入一个内层 while 循环，条件是 currentOr >= k 且 left <= right。这个循环尝试收缩窗口的左边界，以找到最短的可能子数组。
5. 更新最短长度：
   • 在内层循环中，如果当前窗口的长度（right - left + 1）小于 minLength，则更新 minLength。
6. 收缩窗口并更新 currentOr：
   • 为了收缩窗口，需要从当前窗口中移除左边界的元素。代码中的实现方式是通过一个循环从 left + 1 到 right 重新计算 currentOr（这里有一个效率问题，下面会提到）。
   • 更新 currentOr 为不包含左边界元素的新值。
   • 将 left 右移一位，继续尝试收缩窗口。
7. 继续扩展窗口：
   • 完成内层循环后，继续扩展外层循环的右边界，即将 right 右移一位。
8. 返回结果：
   • 循环结束后，检查 minLength 是否仍为 INT_MAX。如果是，说明没有找到符合条件的子数组，返回 -1。
   • 否则，返回 minLength，即符合条件的最短子数组的长度。

效率问题：

• 在收缩窗口的过程中，代码通过一个循环重新计算 currentOr，这实际上是不必要的。可以通过记录移除元素之前的 currentOr 值和移除元素本身，然后使用按位运算直接更新 currentOr，从而提高效率。

优化思路：

• 可以使用一个变量来跟踪上一次计算 currentOr 时左边界元素对 currentOr 的贡献，这样在移除左边界元素时，可以直接通过按位运算减去该贡献，而无需重新计算整个窗口的 currentOr。

原文地址：https://blog.csdn.net/babyiu5201314/article/details/145194170

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