企业官网建设流程全解析

以下是 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];
// 去重：只保留不同的 orValue
if (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 并更新为 cur
free(prev);
prev = cur;
prevSize = curSize;
}

free(prev);
return ans;
}
```

内存优化版本（避免频繁 malloc）

频繁的 malloc/free 会影响性能。可以预分配两个二维数组，交替使用：

```c
int 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.h>

int main() {
int nums1[] = {1, 2, 4};
int nums2[] = {1, 2, 4};

printf("%d\n", minimumDifference(nums1, 3, 3)); // 输出 0
printf("%d\n", minimumDifference(nums2, 3, 6)); // 输出 0

return 0;
}
```

为什么不用滑动窗口？

按位或 不具有单调性：

· 子数组 [l, r] 向右扩展时，or 值单调不减 ✅
· 但向左收缩时，or 值不一定减小（可能保持不变或减少多个位），无法通过双指针维护

因此本题的标准解法是枚举每个右端点下的所有不同 or 值，利用 or 值种类很少 的性质实现高效求解。