使用 C++ 查找总和小于 K 的子数组的数量
c++server side programmingprogramming
在本文中，我们将使用 C++ 查找总和小于 K 的子数组的数量。在这个问题中，我们有一个数组 arr[] 和一个整数 K。所以现在我们必须找到总和小于 K 的子数组。以下是示例 −
输入:arr[] = {1, 11, 2, 3, 15}
K = 10
输出:4
{1}, {2}, {3} 和 {2, 3}
寻找解决方案的方法
现在我们将使用两种不同的方法来解决给定的问题 −
强力
在这种方法中，我们将遍历所有子数组并计算它们的和，如果和小于 k，则与 k 进行比较以增加我们的答案。
示例
#include <bits/stdc++.h>
using namespace std;
int main(){
int arr[] = {1, 11, 2, 3, 15}; // 给定数组
int k = 10; // 给定 k
int size = sizeof(arr) / sizeof(int); // 数组的大小。
int ans = 0; // 计数器变量。
for(int i = 0; i < size; i++){ // 外循环。
int sum = 0;
for(int j = i; j < size; j++){ // 内循环。
sum = sum + arr[j];
if(sum < k) // 与 k 进行比较。
ans++; // 如果 sum 小于 k，则增加我们的 ans。
}
}
cout << ans << "\n";
return 0;
}
输出
4
但是，这种方法并不是很好，因为它的时间复杂度非常高 O(N*N)，其中 n 是数组的大小。
我们将使用滑动窗口方法(这将有助于我们降低程序的时间复杂度)来研究替代解决方案。
高效方法
与蛮力不同，我们不会遍历所有子数组。相反，我们只会在子数组的总和超过 k 时遍历，并将左边界移动到右边界并不断重复，直到遍历整个数组。
示例
#include <bits/stdc++.h>
using namespace std;
int main(){
int arr[] = {1, 11, 2, 3, 15}; // 给定数组
int k = 10; // 给定 k
int size = sizeof(arr) / sizeof(int); // 数组的大小。
int ans = 0; // 计数器变量。
int start = 0; // 左边界。
int end = 0; // 右边界。
int sum = 0;
while(end < size && start < size){ // 直到遍历整个数组。
while(sum >= k && start < end){
sum = sum - arr[start];
start++;
}
if(end >= start)
ans = ans + end - start;
sum += arr[end];
end++;
}
cout << ans << "\n";
return 0;
}
输出
4
我们使用滑动窗口技术来使我们的程序在这种方法中更快或更省时地运行，以应对更大的约束。
上述代码的解释
在这种方法中，我们通常遍历直到我们的总和小于 k，并根据它增加我们的答案，这是当总和大于或等于 k 时代码中的关键变化。在这种情况下，我们开始将左边界增加到比右边界小，或者直到总和大于或等于 k。随着我们进一步处理，它会遍历可以形成的其他子数组。这些总和小于 k 的新子数组被添加到我们的答案中，因此我们的答案会增加。
与我们之前应用的蛮力相比，这种方法非常有效，因为它的时间复杂度为O(N)，其中 N 是数组的大小。
结论
在本文中，我们使用滑动窗口技术解决了一个问题，即找到总和小于 k 的子数组的数量。我们还学习了这个问题的 C++ 程序以及我们解决这个问题的完整方法(正常且有效)。我们可以用其他语言(如 C、java、python 和其他语言)编写相同的程序。希望您觉得这篇文章有用。
