数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究使用 C++ 查找和小于 K 的子数组数量
在本文中，我们将使用 C++ 找出和小于 K 的子数组的数量。在这个问题中，我们有一个数组 arr[] 和一个整数 K。所以现在我们必须找到总和小于 K 的子数组。这是一个例子 -
Input : arr[] = {1, 11, 2, 3, 15}
K = 10
Output : 4
{1}, {2}, {3} and {2, 3}查找解决方案的方法
现在我们将使用两种不同的方法来解决给定的问题 -
暴力法
在这种方法中，我们将遍历所有子数组并计算它们的和，并与 k 进行比较，如果和小于 k 则增加我们的答案。
示例
#include <bits/stdc++.h>
using namespace std;
int main(){
int arr[] = {1, 11, 2, 3, 15}; // given array
int k = 10; // given k
int size = sizeof(arr) / sizeof(int); // size of our array.
int ans = 0; // counter variable.
for(int i = 0; i < size; i++){ // outer loop.
int sum = 0;
for(int j = i; j < size; j++){ // inner loop.
sum = sum + arr[j];
if(sum < k) // comparing with k.
ans++; // incrementing our ans if sum is less than k.
}
}
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}; // given array
int k = 10; // given k
int size = sizeof(arr) / sizeof(int); // size of our array.
int ans = 0; // counter variable.
int start = 0; // left border.
int end = 0; // right border.
int sum = 0;
while(end < size && start < size){ // till the whole array is traversed.
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 和其他语言）编写相同的程序。希望本文对您有所帮助。
964 次查看
