使用 C++ 查找具有 k^m, m >= 0 形式和的子数组的数量
c++server side programmingprogramming
在本文中，我们将解释有关使用 C++ 解决具有 k^m, m >= 0 形式和的子数组的数量的所有内容。给定一个数组 arr[] 和一个整数 K，我们需要找到和的形式为 K^m 且 m 大于等于零的子数组的数量，或者我们可以说我们需要找到和等于 K 的某个非负幂的子数组的数量。
输入:arr[] = { 2, 2, 2, 2 } K = 2
输出:8
具有以下索引的子数组有效:
[1, 1], [2, 2], [3, 3], [4, 4], [1, 2],
[2, 3], [3, 4], [1, 4]
输入:arr[] = { 3, -6, -3, 12 } K = -3
输出:3
主要有两种方法−
强力攻击
在这种方法中，我们将遍历所有子数组并检查它们是否是 K 的某个正整数幂;如果是，则我们增加计数。
示例
#include <bits/stdc++.h>
#define MAX 1000000
using namespace std;
int main(){
int arr[] = {2, 2, 2, 2}; // 给定数组
int k = 2; // 给定整数
int n = sizeof(arr) / sizeof(arr[0]); // 数组的大小
int answer = 0; // 计数器变量
for(int i = 0; i < n; i++){
int sum = 0;
for(int j = i; j < n; j++){ // 此循环将生成所有子数组
sum += arr[j];
int b = 1;
while(b < MAX && sum > b) // k^m Max 应为 10^6
b *= k;
if(b == sum) // 如果 b == sum 则增加计数
answer++;
}
}
cout << answer << "\n";
}
输出
8
但是，这种方法不是很好，因为这个程序的时间复杂度是 O(N*N*log(K))，，其中 N 是数组的大小，K 是用户给出的整数。
这种复杂性并不好，因为这种复杂性可以用于更高的约束，因为如果约束很大，处理将花费太多时间，因此我们将尝试另一种方法，以便我们可以将该程序用于更高的约束。
高效方法
在这种方法中，我们将使用前缀和映射来减少我们的处理，这将大大降低我们的时间复杂度。
示例
#include <bits/stdc++.h>
#define ll long long
#define MAX 1000000
using namespace std;
int main(){
int arr[] = {2, 2, 2, 2}; // 给定的数组
int n = sizeof(arr) / sizeof(arr[0]); // 数组的大小
int k = 2; // 给定的整数
ll prefix_sum[MAX];
prefix_sum[0] = 0;
partial_sum(arr, arr + n, prefix_sum + 1); // 生成前缀和数组
ll sum;
if (k == 1){
// 我们将分别检查 1
sum = 0;
map<ll, int> m;
for (int i = n; i >= 0; i--){
// 如果 m[a+b] = c，则将 c 添加到当前总和中。
if (m.find(prefix_sum[i] + 1) != m.end())
sum += m[prefix_sum[i] + 1];
// 增加前缀和的计数。
m[prefix_sum[i]]++;
}
cout << sum << "\n";
}
else if (k == -1){
// 我们将单独检查 -1
sum = 0;
map<ll, int> m;
for (int i = n; i >= 0; i--){
// 如果 m[a+b] = c，则将 c 添加到当前总和中。
if (m.find(prefix_sum[i] + 1) != m.end())
sum += m[prefix_sum[i] + 1];
if (m.find(prefix_sum[i] - 1) != m.end())
sum += m[prefix_sum[i] - 1];
// 增加前缀和的计数。
m[prefix_sum[i]]++;
}
cout << sum << "\n";
}
else{
sum = 0;
ll b;
map<ll, int> m;
for (int i = n; i >= 0; i--){
b = 1;
while (b < MAX){ // 我们不会检查是否超过 10^6
// 如果 m[a+b] = c，则将 c 添加到当前总和中。
if (m.find(prefix_sum[i] + b) != m.end())
sum += m[prefix_sum[i] + b];
b *= k;
}
m[prefix_sum[i]]++;
}
cout << sum << &"\n";
}
return 0;
}
输出
8
结论
我们解决了一个问题，以 O(nlog(k)log(n)) 的时间复杂度找到总和为 k^m 且 m >= 0 的子数组的数量。我们还学习了这个问题的 C++ 程序以及我们解决这个问题的完整方法(正常和高效)。我们可以用其他语言(如 C、java、python 和其他语言)编写相同的程序。希望您觉得这篇文章有用。
