使用C++编写，找到和为k^m形式的子数组数量，其中m >= 0

在本文中，我们将解释有关在 C++ 中求解总和为 k^m, m >= 0 的子数组数量的所有内容。给定一个数组 arr[] 和一个整数 K，我们需要找到具有 K^m 形式的和的子数组的数量，其中 m 大于等于 0，或者我们可以说我们需要找到具有 K^m 形式的子数组的数量总和等于 K 的某个非负幂。

Input: arr[] = { 2, 2, 2, 2 } K = 2

Output: 8

Sub-arrays with below indexes are valid:
[1, 1], [2, 2], [3, 3], [4, 4], [1, 2],
[2, 3], [3, 4], [1, 4]

Input: arr[] = { 3, -6, -3, 12 } K = -3

Output: 3

主要有两种方法 -

暴力破解

在这种方法中，我们将遍历所有子数组并检查它们是否是K 与否；如果是，则我们增加计数。

示例

#include 
#define MAX 1000000
using namespace std;
int main(){
   int arr[] = {2, 2, 2, 2}; // given array
   int k = 2; // given integer
   int n = sizeof(arr) / sizeof(arr[0]); // the size of our array
   int answer = 0; // counter variable
   for(int i = 0; i < n; i++){
      int sum = 0;
      for(int j = i; j < n; j++){ // this will loop will make all the subarrays
         sum += arr[j];
         int b = 1;
         while(b < MAX && sum > b) // k^m Max should be 10^6
            b *= k;
         if(b == sum) // if b == sum then increment count
            answer++;
      }
   }
   cout << answer << "\n";
}

输出

8

但是，这种方法并不是很好，因为该程序的时间复杂度为O(N*N*log(K))，，其中 N 是数组的大小，K 是数组的大小。用户给定的整数。

立即学习“C++免费学习笔记（深入）”；

英特尔AI工具

英特尔AI与机器学习解决方案

下载

这种复杂性不好，因为这种复杂性可以用于更高的约束，因为如果约束很大，则需要花费太多时间来处理，因此我们将尝试另一种方法，以便我们可以使用该程序来实现更高的约束。

高效方法

在这种方法中，我们将使用前缀和和映射来减少处理，从而大大降低时间复杂度。

示例

#include 
#define ll long long
#define MAX 1000000
using namespace std;
int main(){
   int arr[] = {2, 2, 2, 2}; // The given array
   int n = sizeof(arr) / sizeof(arr[0]); // size of our array
   int k = 2; // given integer
   ll prefix_sum[MAX];
   prefix_sum[0] = 0;
   partial_sum(arr, arr + n, prefix_sum + 1); // making prefix sum array
   ll sum;
   if (k == 1){
   // we are going to check separately for 1
      sum = 0;
      map m;
   for (int i = n; i >= 0; i--){
      // If m[a+b] = c, then add c to the current sum.
      if (m.find(prefix_sum[i] + 1) != m.end())
         sum += m[prefix_sum[i] + 1];
         // Increase count of prefix sum.
         m[prefix_sum[i]]++;
      }
      cout << sum << "\n";
   }
   else if (k == -1){
      // we are going to check separately for -1
      sum = 0;
      map m;
      for (int i = n; i >= 0; i--){
         // If m[a+b] = c, then add c to the current sum.
         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];

         // Increase count of prefix sum.
         m[prefix_sum[i]]++;
      }
      cout << sum << "\n";
   }
   else{
      sum = 0;
      ll b;
      map m;
      for (int i = n; i >= 0; i--){
         b = 1;
         while (b < MAX){ // we are not going to check for more than 10^6
            // If m[a+b] = c, then add c to the current sum.
            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

结论

我们解决了一个问题，找到总和为 k^m 形式的子数组的数量，其中 m >= 0，时间复杂度为 O(nlog(k)log(n))时间复杂度。我们还学习了解决这个问题的C++程序以及解决这个问题的完整方法（正常且高效）。我们可以用其他语言比如C、java、python等语言来编写同样的程序。希望这篇文章对您有所帮助。