DeepSeek LeetCode 3171. 找到按位或最接近 K 的子数组 C语言实现

以下是 LeetCode 3171 的 C 语言实现。C 语言需要手动管理动态数组核心思路与 Java 版本完全一致维护以当前元素结尾的所有不同或值。c#include stdio.h#include stdlib.h#include limits.h// 存储 (orValue, leftIndex)typedef struct {int orValue;int leftIdx;} Pair;int minimumDifference(int* nums, int numsSize, int k) {// prev 存储上一个右端点产生的不同或值Pair* prev (Pair*)malloc(numsSize * sizeof(Pair));int prevSize 0;int ans INT_MAX;for (int i 0; i numsSize; i) {// cur 存储当前右端点产生的不同或值Pair* cur (Pair*)malloc(numsSize * sizeof(Pair));int curSize 0;// 当前元素单独成为一个子数组cur[curSize].orValue nums[i];cur[curSize].leftIdx i;curSize;// 合并之前的或值for (int j 0; j prevSize; j) {int newVal prev[j].orValue | nums[i];// 去重只保留不同的 orValueif (cur[curSize - 1].orValue ! newVal) {cur[curSize].orValue newVal;cur[curSize].leftIdx prev[j].leftIdx;curSize;}}// 更新答案for (int j 0; j curSize; j) {int diff abs(cur[j].orValue - k);if (diff ans) {ans diff;}}// 释放 prev 并更新为 curfree(prev);prev cur;prevSize curSize;}free(prev);return ans;}内存优化版本避免频繁 malloc频繁的 malloc/free 会影响性能。可以预分配两个二维数组交替使用cint minimumDifference(int* nums, int numsSize, int k) {// 每个右端点最多产生 32 种不同或值int 型 31 个有效位int prevVals[32], prevLefts[32];int prevSize 0;int curVals[32], curLefts[32];int ans INT_MAX;for (int i 0; i numsSize; i) {int curSize 0;// 当前元素单独成为子数组curVals[curSize] nums[i];curLefts[curSize] i;curSize;// 合并 prev 中的或值for (int j 0; j prevSize; j) {int newVal prevVals[j] | nums[i];if (curVals[curSize - 1] ! newVal) {curVals[curSize] newVal;curLefts[curSize] prevLefts[j];curSize;}}// 更新答案for (int j 0; j curSize; j) {int diff abs(curVals[j] - k);if (diff ans) ans diff;}// 交换 cur 和 prev为下一轮准备// 方式1直接复制数组prevSize curSize;for (int j 0; j curSize; j) {prevVals[j] curVals[j];prevLefts[j] curLefts[j];}}return ans;}核心要点说明特性 说明时间复杂度 O(n·logU)U max(nums) ≤ 2×10⁹logU ≤ 31空间复杂度 O(logU)使用固定大小 32 的数组去重条件 curVals[curSize-1] ! newVal确保只保留不同的 or 值leftIdx 作用 虽然这里没用于剪枝但保留它可用于其他扩展需求如求最小区间长度示例验证c// 测试代码#include stdio.hint main() {int nums1[] {1, 2, 4};int nums2[] {1, 2, 4};printf(%d\n, minimumDifference(nums1, 3, 3)); // 输出 0printf(%d\n, minimumDifference(nums2, 3, 6)); // 输出 0return 0;}为什么不用滑动窗口按位或 不具有单调性· 子数组 [l, r] 向右扩展时or 值单调不减 ✅· 但向左收缩时or 值不一定减小可能保持不变或减少多个位无法通过双指针维护因此本题的标准解法是枚举每个右端点下的所有不同 or 值利用 or 值种类很少 的性质实现高效求解。