从暴力到优化：解决「分数严格小于k的子数组数目」问题

问题描述

给定一个正整数数组 nums 和一个整数 k，我们需要统计数组中所有分数严格小于 k 的非空连续子数组的数目。子数组的分数定义为子数组的和乘以子数组的长度。

例如，对于数组 [1, 2, 3, 4, 5]，子数组 [1, 2, 3] 的分数为 (1+2+3)*3 = 18。

初步思考：暴力解法

最直观的解法是枚举所有可能的子数组，计算每个子数组的分数，然后统计满足条件的子数组数目。

java

public int countSubarrays(int[] nums, int k) {int count = 0;int n = nums.length;for (int i = 0; i < n; i++) {for (int j = i; j < n; j++) {long sum = 0;for (int m = i; m <= j; m++) {sum += nums[m];}long score = sum * (j - i + 1);if (score < k) {count++;}}}return count;
}

时间复杂度分析：三重循环，时间复杂度为 O(n³)，对于较大的 n（如 n=10⁵），这种解法显然会超时。

第一次优化：前缀和

观察到在暴力解法中，我们重复计算了很多子数组的和。可以使用前缀和数组来优化求和过程。

java

public int countSubarrays(int[] nums, int k) {int count = 0;int n = nums.length;long[] prefixSum = new long[n + 1];for (int i = 0; i < n; i++) {prefixSum[i + 1] = prefixSum[i] + nums[i];}for (int i = 0; i < n; i++) {for (int j = i; j < n; j++) {long sum = prefixSum[j + 1] - prefixSum[i];long score = sum * (j - i + 1);if (score < k) {count++;}}}return count;
}

优化效果：将时间复杂度从 O(n³) 降到了 O(n²)，但对于 n=10⁵ 仍然不够高效。

第二次优化：提前终止内层循环

注意到数组元素都是正整数，当子数组的和已经很大时，继续扩展子数组只会使分数更大。因此可以在内层循环中提前终止。

java

public int countSubarrays(int[] nums, int k) {int count = 0;int n = nums.length;for (int i = 0; i < n; i++) {long sum = 0;for (int j = i; j < n; j++) {sum += nums[j];long score = sum * (j - i + 1);if (score < k) {count++;} else {break; // 提前终止}}}return count;
}

优化效果：虽然最坏情况下时间复杂度仍是 O(n²)，但对于实际数据通常会有更好的表现。

最优解：滑动窗口法

观察到当固定右端点 j 时，随着左端点 i 的增加，子数组的和和长度都单调递减，因此子数组的分数也单调递减。这提示我们可以使用滑动窗口技术。

java

class Solution {public long countSubarrays(int[] nums, long k) {long res = 0;long total = 0;int left = 0;for (int right = 0; right < nums.length; right++) {total += nums[right];while (total * (right - left + 1) >= k) {total -= nums[left];left++;}res += right - left + 1;}return res;}
}

算法分析：

1. 初始化窗口左边界 left=0，结果 res=0

2. 遍历数组，right 作为窗口右边界

3. 将 nums[right] 加入当前窗口和 total

4. 当窗口分数 ≥k 时，移动左边界 left 直到分数 <k

5. 以 right 结尾的满足条件的子数组数目为 right-left+1

6. 累加到 res 中

时间复杂度：O(n)，每个元素最多被处理两次（加入窗口和移出窗口）

关键点总结

1. 暴力解法容易想到但效率低下，适合作为思考起点

2. 前缀和优化减少了重复计算，但仍不够高效

3. 提前终止利用了正整数的性质，实际效果不错

4. 滑动窗口是最优解，利用了单调性将复杂度降到 O(n)

常见错误与调试

1. 整数溢出：当 n 很大时，sum 和 score 可能超出 int 范围，要使用 long

2. 边界条件：空数组、k=0 等特殊情况要处理

3. 等号处理：题目要求严格小于 k，注意不要包含等于的情况

扩展思考

如果将问题改为「分数小于等于 k」，解法需要如何调整？如果数组包含负数，又该如何处理？这些问题留给读者思考。

总结

通过这个问题，我们展示了从暴力解法到最优解的完整优化过程。关键在于发现问题的单调性特征，并应用滑动窗口技术。这种循序渐进的分析方法可以应用于许多类似的算法问题。