和为完全平方的子数组的数量

原文：https://www.geeksforgeeks.org/count-of-subarrays-whose-sum-is-a-perfect-square/

给定具有正负元素的数组arr[]，任务是对所有和为完全平方的子数组进行计数。

示例：

输入：arr[] = {2, 3, -5, 6, -7, 4}

输出：5

说明：

子数组{2, 3, -5}, {-5, 6}, {3, -5, 6 }, {3, -5, 6, -7, 4}, {4}的和分别为 0、1、4、1 和 4，它们具有完美的平方和。

输入：arr [] = {3，-6，4，-2，7}

输出：3

说明：{3, -6, 4}, {4}, {4, -2, 7}是具有完美平方和的子数组。

朴素的方法：

一个简单的解决方案是生成所有可能的子数组。 遍历时，请跟踪子数组总和。 记录所有和为完全平方的子数组。

高效解决方案：想法是使用前缀和数组解决给定的问题。

  • 创建一个prefixSum数组并存储其前缀和。

  • 遍历prefixSum数组并确定其最小值，即prefixMin。

  • 现在，创建一个无序映射，该遍历可用于存储当前prefixSum的频率，同时遍历prefixSum数组。

  • 用值 1 初始化映射的第 0 个键索引，因为 0 是一个完美的正方形。

  • 用嵌套循环遍历prefixSum数组。

  • 对于每个prefixSum元素，嵌套循环将查找mapKey = (prefixSum[i] – j * j)（如果在映射索引中可用）。

  • 如果prefixSum[i] – j * j在映射中已经可用，我们将使用prefixSum[i] – j * j的索引值更新计数器。

  • 这个想法是用所有平方j * j检查当前prefixSum值，直到差达到prefixMin为止。

  • 现在，随着外循环的每次迭代，将映射的当前前缀和的索引加 1。

  • 基本概念是我们继续从prefixSum[i] – j * j中搜索，因为如果一部分是数组，则是prefixSum[i] – j * j ，则数组的另一部分将是j * j，即一个完美的平方和。

  • 出于此目的，您可以在上图中看到totalSum实际上是prefixSum。

下面是上述方法的实现：

C++

// C++ code for the above approach.
#include <bits/stdc++.h>
using namespace std;

#define lli long long int

// Function to find count of subarrays
// whose sum is a perfect square.
lli countSubarrays(int arr[],
                   int n)
{
    // to search for index with
    // (current prefix sum - j*j)
    unordered_map<int, int> mp;

    // storing the prefix sum
    int prefixSum[n];

    // used to track the minimum
    // value in prefixSum
    int prefixMin = 0;

    prefixSum[0] = arr[0];
    prefixMin = min(prefixMin,
                    prefixSum[0]);

    // Calculating the prefixSum
    // and tracking the prefixMin
    for (int i = 1; i < n; i++) {

        prefixSum[i] = prefixSum[i - 1]
                       + arr[i];

        // below statement is used if
        // array contains
        // negative numbers
        prefixMin = min(prefixMin,
                        prefixSum[i]);
    }

    // counts the no of subarrays
    // with perfect square sum
    lli countSubs = 0;

    // as 0 is a perfect square,
    // so we initialize 0th
    // index-key with value 1
    mp[0] = 1;

    // Here we count the perfect
    // square subarray sum by
    // searching if there is a
    // prefix with
    // sum = (current prefixSum - (sq*sq))
    for (int i = 0; i < n; i++) {
        for (int j = 0;
             prefixSum[i] - j * j >= prefixMin;
             j++) {

            if (mp.find(prefixSum[i] - j * j)
                != mp.end())

                // increasing our subarray count
                countSubs += mp[prefixSum[i]
                                - j * j];
        }

        // increasing the current prefixSum
        // index value in map by 1 to count
        // the other perfect squares while
        // traversing further
        mp[prefixSum[i]]++;
    }

    return countSubs;
}

// Driver code
int main()
{
    int arr[] = { 2, 3, -5,
                  6, -7, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);

    lli ans = countSubarrays(arr, n);

    // printing the result
    cout << ans;

    return 0;
}

Java

// Java code for 
// the above approach.
import java.util.*;
class GFG{

// Function to find count of 
// subarrays whose sum is 
// a perfect square.
static long countSubarrays(int arr[], 
                           int n)
{
  // To search for index with
  // (current prefix sum - j*j)
  HashMap<Integer,
          Integer> mp = new HashMap<Integer,
                                    Integer>();

  // Storing the prefix sum
  int []prefixSum = new int[n];

  // Used to track the minimum
  // value in prefixSum
  int prefixMin = 0;

  prefixSum[0] = arr[0];
  prefixMin = Math.min(prefixMin,
                       prefixSum[0]);

  // Calculating the prefixSum
  // and tracking the prefixMin
  for (int i = 1; i < n; i++) 
  {
    prefixSum[i] = prefixSum[i - 1] + arr[i];

    // Below statement is used if
    // array contains
    // negative numbers
    prefixMin = Math.min(prefixMin,
                         prefixSum[i]);
  }

  // Counts the no of subarrays
  // with perfect square sum
  long countSubs = 0;

  // As 0 is a perfect square,
  // so we initialize 0th
  // index-key with value 1
  mp.put(0, 1);

  // Here we count the perfect
  // square subarray sum by
  // searching if there is a
  // prefix with
  // sum = (current prefixSum - (sq*sq))
  for (int i = 0; i < n; i++) 
  {
    for (int j = 0; 
             prefixSum[i] - j * 
             j >= prefixMin; j++) 
    {
      if (mp.containsKey(prefixSum[i] - j * j))

        // Increasing our subarray count
        countSubs += mp.get(prefixSum[i] - 
                            j * j);
    }

    // Increasing the current prefixSum
    // index value in map by 1 to count
    // the other perfect squares while
    // traversing further
    if(mp.containsKey(prefixSum[i]))
    {
      mp.put(prefixSum[i], 
      mp.get(prefixSum[i]) + 1);
    }
    else
    {
      mp.put(prefixSum[i], 1);
    }
  }

  return countSubs;
}

// Driver code
public static void main(String[] args)
{
  int arr[] = {2, 3, -5,
               6, -7, 4};
  int n = arr.length;
  long ans = countSubarrays(arr, n);

  // Printing the result
  System.out.print(ans);
}
}

// This code is contributed by Princi Singh

Python3

# Python3 code for the above approach.
from collections import defaultdict

# Function to find count of subarrays 
# whose sum is a perfect square.
def countSubarrays(arr, n):

    # To search for index with 
    # (current prefix sum - j*j)
    mp = defaultdict(lambda:0)

    # Storing the prefix sum
    prefixSum = [0] * n

    # Used to track the minimum 
    # value in prefixSum
    prefixMin = 0

    prefixSum[0] = arr[0]
    prefixMin = min(prefixMin, prefixSum[0])

    # Calculating the prefixSum 
    # and tracking the prefixMin
    for i in range(1, n):
        prefixSum[i] = prefixSum[i - 1] + arr[i]

        # Below statement is used if 
        # array contains negative numbers 
        prefixMin = min(prefixMin, prefixSum[i])

    # Counts the no of subarrays 
    # with perfect square sum
    countSubs = 0

    # As 0 is a perfect square, 
    # so we initialize 0th 
    # index-key with value 1 
    mp[0] = 1

    # Here we count the perfect 
    # square subarray sum by 
    # searching if there is a 
    # prefix with 
    # sum = (current prefixSum - (sq*sq))
    for i in range(n):
        j = 0

        while prefixSum[i] - j * j >= prefixMin:
            if prefixSum[i] - j * j in mp:

                # Increasing our subarray count
                countSubs += mp[prefixSum[i] - j * j]
            j += 1

        # Increasing the current prefixSum 
        # index value in map by 1 to count 
        # the other perfect squares while 
        # traversing further 
        mp[prefixSum[i]] += 1

    return countSubs

# Driver code
arr = [ 2, 3, -5, 6, -7, 4 ]
n = len(arr)
ans = countSubarrays(arr, n)

# Printing the result
print(ans)

# This code is contributed by Shivam Singh

输出： 

5

时间复杂度：O(N * sqrt(K))。

辅助空间：O(n)。

版权属于：月萌API www.moonapi.com，转载请注明出处

本文链接：https://moonapi.com/news/33224.html