首页 > 后端开发 > C++ > 正文

使用C++编写,找到和小于K的子数组的数量

WBOY
发布: 2023-09-07 15:25:02
转载
1445 人浏览过

使用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 是数组的大小。

我们'将使用滑动窗口方法寻找替代解决方案(这将帮助我们降低程序的时间复杂度)。

高效方法

暴力破解不同

高效方法

strong>,我们不会遍历所有子数组。相反,只有当子数组的总和超过 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。随着我们的处理进一步进行,它遍历了其他可能形成的子数组。这些新的子数组的总和小于k被添加到我们的答案中,因此我们的答案递增。

与之前的暴力解法相比,这种方法非常高效,因为它的时间复杂度为O(N),其中N是我们数组的大小。

结论

在本文中,我们使用滑动窗口技术解决了一个问题,即找到和小于k的子数组的数量。我们还学习了这个问题的C++程序以及我们解决这个问题的完整方法(普通和高效)。我们可以使用其他语言(如C、Java、Python和其他语言)编写相同的程序。希望您会发现本文有帮助。

以上是使用C++编写,找到和小于K的子数组的数量的详细内容。更多信息请关注PHP中文网其他相关文章!

相关标签:
来源:tutorialspoint.com
本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责声明 Sitemap
PHP中文网:公益在线PHP培训,帮助PHP学习者快速成长!