DeepSeek LeetCode 3261. 统计满足 K 约束的子字符串数量 II Java实现
这道题是 LeetCode 3261. 统计满足 K 约束的子字符串数量 II，要求高效处理多个查询，统计每个查询区间内满足 K 约束的子串数量。
题目回顾
K 约束定义：字符串中 '0' 或 '1' 的个数 不超过 K。
关键难点：需要 O(1) 或 O(log n) 处理每个查询，不能暴力枚举。
解题思路
1. 找到每个位置 i 作为左端点时，最远可以到达的右端点
对于每个左端点 left，找到最大的 right 使得 [left, right] 满足 K 约束。
利用滑动窗口（双指针）在 O(n) 内完成。
2. 构建前缀和数组
设 maxRight[i] = 以 i 为左端点的最大可行右端点（包含）。
对于查询 [l, r]，对于左端点 i 在 [l, r] 范围内：
· 如果 maxRight[i] >= r，说明以 i 开头的子串从 i 到 r 都满足，贡献 (r - i + 1) 个。
· 如果 maxRight[i] < r，贡献 (maxRight[i] - i + 1) 个。
但直接遍历会超时，需要优化。
3. 前缀和 + 二分查找优化
由于 maxRight 数组单调不减（可以用滑动窗口证明），我们可以：
· 预处理 prefixSum[i] 表示以 0..i 为左端点的累计子串数。
· 对于查询 [l, r]，二分找到最后一个位置 p 使得 maxRight[p] < r。
· 那么：
· 对于左端点 i ∈ [l, p]，每个贡献 (maxRight[i] - i + 1)
· 对于左端点 i ∈ [p+1, r]，每个贡献 (r - i + 1)
两部分都能用前缀和快速计算。
Java 实现
```java
class Solution {
public long[] countKConstraintSubstrings(String s, int k, int[][] queries) {
int n = s.length();
char[] arr = s.toCharArray();
// 1. 滑动窗口计算 maxRight[i]
int[] maxRight = new int[n];
int[] cnt = new int[2]; // cnt[0] 数0的个数，cnt[1] 数1的个数
int right = 0;
for (int left = 0; left < n; left++) {
while (right < n && (cnt[0] + (arr[right] == '0' ? 1 : 0) <= k ||
cnt[1] + (arr[right] == '1' ? 1 : 0) <= k)) {
cnt[arr[right] - '0']++;
right++;
}
maxRight[left] = right - 1; // 以 left 开头最远可到的位置
// 移除 left 位置的字符，为下一次循环做准备
cnt[arr[left] - '0']--;
}
// 2. 前缀和数组 preSum[i] = sum_{j=0}^{i-1} (maxRight[j] - j + 1)
long[] preSum = new long[n + 1];
for (int i = 0; i < n; i++) {
preSum[i + 1] = preSum[i] + (maxRight[i] - i + 1);
}
// 3. 处理查询
long[] res = new long[queries.length];
for (int idx = 0; idx < queries.length; idx++) {
int l = queries[idx][0];
int r = queries[idx][1];
// 二分查找最后一个位置 p 满足 maxRight[p] < r
int low = l, high = r, p = l - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (maxRight[mid] < r) {
p = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
long total = 0;
if (p >= l) {
// 左端点 i ∈ [l, p]，贡献 (maxRight[i] - i + 1)
total += preSum[p + 1] - preSum[l];
}
if (p + 1 <= r) {
// 左端点 i ∈ [p+1, r]，贡献 (r - i + 1)
long len = r - (p + 1) + 1;
total += len * (len + 1) / 2;
}
res[idx] = total;
}
return res;
}
}
```
复杂度分析
· 时间复杂度：O(n + q log n)，n 是字符串长度，q 是查询数量。
· 滑动窗口 O(n)
· 预处理前缀和 O(n)
· 每个查询二分查找 O(log n)
· 空间复杂度：O(n)，存储 maxRight 和 preSum。
示例验证
```java
// 示例
String s = "000111";
int k = 1;
int[][] queries = {{0, 5}};
// 输出: [10]
// 解释: 满足 K 约束的子串有:
// "0","0","0","1","1","1","00","01","10","11" 等共10个
```
这个解法利用了滑动窗口的单调性和前缀和，在 LeetCode 上可以通过所有测试。