这道题是 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 ∈ [p1, r]每个贡献 (r - i 1)两部分都能用前缀和快速计算。Java 实现javaclass 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_{j0}^{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] rint 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 ∈ [p1, 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 上可以通过所有测试。