Recuento de subarreglos con suma única con suma como máximo K

Dada una array arr[] de tamaño N y un entero K ., la tarea es contar el número de subarreglos con suma única con suma como máximo K.

Ejemplos :

Entrada : N = 3, arr[] = {1, 0, 1}, K = 1
Salida : 3
Explicación : Todos los subarreglos son [1], [0], [1], [1, 0], [0, 1], [1, 0, 1] & La suma de estos subarreglos son {1, 0, 1, 1, 1, 2} respectivamente. Solo hay 2 sumas posibles distintas menores o iguales a 1
Entrada : N = 1, arr[] = {1}, K = 0
Salida : 0

Enfoque : La tarea se puede resolver calculando sumas de cada subarreglo y almacenándolos en un HashMap . Iterar sobre HashMap e incrementar el conteo, si la suma es como máximo K

A continuación se muestra la implementación del enfoque anterior.

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate the valid sums
void solve(int arr[], int n, int k)
{
 
    // Store the distinct subarray sums
    unordered_map<int, int> occ;
 
    int cur = 0;
    for (int i = 0; i < n; i++) {
        cur = 0;
        for (int j = i; j < n; j++) {
            cur += arr[j];
            occ[cur]++;
        }
    }
 
    // Stores the answer
    int ans = 0;
    for (auto x : occ) {
        if (x.first <= k)
            ans++;
    }
 
    cout << ans << endl;
}
 
// Driver Code
int main()
{
    int N = 3, K = 1;
    int arr[3] = { 1, 0, 1 };
 
    solve(arr, N, K);
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to calculate the valid sums
static void solve(int arr[], int n, int k)
{
 
    // Store the distinct subarray sums
    HashMap<Integer,Integer> occ = new HashMap<Integer,Integer>();
 
    int cur = 0;
    for (int i = 0; i < n; i++) {
        cur = 0;
        for (int j = i; j < n; j++) {
            cur += arr[j];
            if(occ.containsKey(cur)){
                occ.put(cur, occ.get(cur)+1);
            }
            else{
                occ.put(cur, 1);
            }
        }
    }
 
    // Stores the answer
    int ans = 0;
    for (Map.Entry<Integer,Integer> x : occ.entrySet()) {
        if (x.getKey() <= k)
            ans++;
    }
 
    System.out.print(ans +"\n");
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 3, K = 1;
    int arr[] = { 1, 0, 1 };
 
    solve(arr, N, K);
}
}
 
// This code is contributed by 29AjayKumar

# python program for the above approach
 
# Function to calculate the valid sums
def solve(arr, n, k):
 
    # Store the distinct subarray sums
    occ = {}
 
    cur = 0
    for i in range(0, n):
        cur = 0
        for j in range(i, n):
            cur += arr[j]
            if cur in occ:
                occ[cur] += 1
            else:
                occ[cur] = 1
 
        # Stores the answer
    ans = 0
    for x in occ:
        if (x <= k):
            ans += 1
 
    print(ans)
 
# Driver Code
if __name__ == "__main__":
    N = 3
    K = 1
 
    arr = [1, 0, 1]
    solve(arr, N, K)
 
    # This code is contributed by rakeshsahni

// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
   
    // Function to calculate the valid sums
    static void solve(int[] arr, int n, int k)
    {
 
        // Store the distinct subarray sums
        Dictionary<int, int> occ
            = new Dictionary<int, int>();
 
        int cur = 0;
        for (int i = 0; i < n; i++) {
            cur = 0;
            for (int j = i; j < n; j++) {
                cur += arr[j];
                if (!occ.ContainsKey(cur))
                    occ[cur] = 0;
                else
                    occ[cur]++;
            }
        }
 
        // Stores the answer
        int ans = 0;
        foreach(KeyValuePair<int, int> x in occ)
        {
            if (x.Key <= k)
                ans++;
        }
 
        Console.WriteLine(ans);
    }
 
    // Driver Code
    public static void Main()
    {
        int N = 3, K = 1;
        int[] arr = { 1, 0, 1 };
 
        solve(arr, N, K);
    }
}
 
// This code is contributed by ukasp.

<script>
 
// JavaScript code for the above approach
       
// Function to calculate the valid sums
function solve(arr, n, k)
{
     
    // Store the distinct subarray sums
    let occ = new Map();
 
    let cur = 0;
    for(let i = 0; i < n; i++)
    {
        cur = 0;
        for(let j = i; j < n; j++)
        {
            cur += arr[j];
            if (occ.has(cur))
            {
                occ.set(cur, occ.get(cur) + 1)
            }
            else
            {
                occ.set(cur, 1);
            }
        }
    }
 
    // Stores the answer
    let ans = 0;
    for(let[key, value] of occ)
    {
        if (key <= k)
            ans++;
    }
    document.write(ans + '<br>');
}
 
// Driver Code
let N = 3, K = 1;
let arr = [ 1, 0, 1 ];
 
solve(arr, N, K);
 
// This code is contributed by Potta Lokesh
 
</script>

2

Complejidad de Tiempo : O(N ² )
Espacio Auxiliar : O(N)