阅读 139

使用 C++ 查找总和小于 K 的子数组的数量

在本文中,我们将使用 C++ 找出总和小于 K 的子数组的数量。在这个问题中,我们有一个数组 arr[] 和一个整数 K。所以现在我们必须找到总和小于 K 的子数组。这是示例 -


Input : arr[] = {1, 11, 2, 3, 15}K = 10Output : 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}; // 给定数组    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 是我们数组的大小。

我们将查看使用滑动窗口的替代解决方案method(That will help us decrease the time complexity of the program)。

有效的方法

Brute Force不同,我们不会遍历所有子数组。相反,只有当子数组的总和超过 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 和其他语言。希望这篇文章对您有所帮助。


文章分类
百科问答
版权声明:本站是系统测试站点,无实际运营。本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 XXXXXXo@163.com 举报,一经查实,本站将立刻删除。
相关推荐