സുബാരെ തുക k


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു അഡോബി ആമസോൺ അമേരിക്കൻ എക്സ്പ്രസ് ബ്ലൂംബർഗ് ബെ ഫേസ്ബുക്ക് ഗോൾഡ്മാൻ സാക്സ് ഗൂഗിൾ മൈക്രോസോഫ്റ്റ് ട്വിలియో യാഹൂ
അറേ ഹാഷ്

ഒരു പൂർണ്ണസംഖ്യ നൽകി ശ്രേണി ഒരു പൂർണ്ണസംഖ്യ k. മൂലകങ്ങളുടെ ആകെത്തുക k ന് തുല്യമായ തന്നിരിക്കുന്ന അറേയുടെ തുടർച്ചയായ സബ്‌റേകളുടെ എണ്ണം കണ്ടെത്തുക.

ഉള്ളടക്ക പട്ടിക

ഉദാഹരണം

Input 1: arr[] = {5,0,5,10,3,2,-15,4}
         k = 5
Output:  7

Input 2: arr[] = {1,1,1,2,4,-2}
         k = 2
Output:  4

വിശദീകരണം: മുകളിൽ കൊടുത്തിരിക്കുന്ന ഉദാഹരണം -1 പരിഗണിക്കുക, ചുവടെയുള്ള ചിത്രം തന്നിരിക്കുന്ന തുക k (= 5) ഉള്ള എല്ലാ സബ്‌റേകളെയും എടുത്തുകാണിക്കുന്നു.

സബ്‌റേ തുക k ന് തുല്യമാണ്

പരിഹാര തരങ്ങൾ

  1. ബ്രൂട്ട് ഫോഴ്സ് / നിഷ്കളങ്കം
  2. സഞ്ചിത തുക ഉപയോഗിക്കുന്നു
  3. അധിക ഇടം ഉപയോഗിക്കാതെ
  4. ഹാഷ് മാപ്പ് ഡാറ്റ ഘടന ഉപയോഗിക്കുന്നു

ബ്രൂട്ട് ഫോഴ്സ് / നിഷ്കളങ്കം

സമീപനം

തന്നിരിക്കുന്ന അറേയുടെ എല്ലാ സബ്‌റേകളും ജനറേറ്റുചെയ്യുകയും സബ്‌റേയുടെ മൂലകങ്ങളുടെ ആകെത്തുക നൽകിയ k ന് തുല്യമാണോയെന്ന് പരിശോധിക്കുകയുമാണ് ആശയം. സബ്‌റേ മൂലകങ്ങളുടെ ആകെത്തുക നൽകിയ k ന് തുല്യമാണെങ്കിൽ അതിന്റെ മൂല്യം വർദ്ധിപ്പിക്കുക എണ്ണുക ആവശ്യമായ ഫലം സംഭരിക്കാൻ ഉപയോഗിക്കുന്നു.

അൽഗോരിതം

  1. ശ്രേണിയിൽ നിന്ന് [0 മുതൽ n-1] ബാഹ്യ ലൂപ്പ് പ്രവർത്തിപ്പിക്കുക. ലൂപ്പ് വേരിയബിൾ ആണ് ആരംഭിക്കുക.
  2. ശ്രേണിയിൽ നിന്ന് ആന്തരിക ലൂപ്പ് പ്രവർത്തിപ്പിക്കുക [ആരംഭിക്കുക + 1, n]. ലൂപ്പ് വേരിയബിൾ ആണ് അവസാനം.
  3. ശ്രേണിയിൽ നിന്ന് മുകളിലുള്ള ലൂപ്പിലേക്ക് നെസ്റ്റുചെയ്‌ത ഒരു ലൂപ്പ് പ്രവർത്തിപ്പിക്കുക [ആരംഭിക്കുക, അവസാനം -1] കണക്കാക്കുക തുക ഈ ശ്രേണിയിൽ.
  4. തന്നിരിക്കുന്ന k ന് തുക തുല്യമാണെങ്കിൽ, അതിന്റെ മൂല്യം വർദ്ധിപ്പിക്കുക എണ്ണുക.

മുകളിലുള്ള അൽ‌ഗോരിതം ചുവടെ ചിത്രീകരിച്ചിരിക്കുന്നു:

സബ്‌റേ തുക k ന് തുല്യമാണ് സബ്‌റേ തുക k ന് തുല്യമാണ് സബ്‌റേ തുക k ന് തുല്യമാണ് സബ്‌റേ തുക k ന് തുല്യമാണ് സബ്‌റേ തുക k ന് തുല്യമാണ് സബ്‌റേ തുക k ന് തുല്യമാണ്

മുകളിലുള്ള ചിത്രങ്ങളിൽ നിന്ന്, മൊത്തം 7 സബ്‌റേകളിലുണ്ടെന്ന് ഞങ്ങൾ നിരീക്ഷിക്കുന്നു (ഇതിൽ ഹൈലൈറ്റ് ചെയ്തിരിക്കുന്നു ചുവന്ന) നൽകിയ തുക (k = 5).

നടപ്പിലാക്കൽ

സി ++ പ്രോഗ്രാം ഫോർ സബാരേ തുക k ന് തുല്യമാണ്

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// function to find number of subarrays with sum = k
int subArraySum(vector <int> arr,int k)
{
    int n = arr.size();
    int count = 0;
    
    // generate all the subarrays
    // a given subarray within range [start,end]
    // is chosen
    for(int start=0;start<n;start++)
    {
        for(int end=start+1;end<=n;end++)
        {
            int sum = 0;
            
            // find sum of the elements in range[start,end]
            for(int i=start;i<end;i++)
            sum += arr[i];
            
            // if the given sum equals to k 
            // then increment the required count value
            if(sum == k)
            count++;
            
        }
    }
    return count;
}

// main program to implement above functions
int main() 
{
    vector <int> arr = {5,0,5,10,3,2,-15,4};
    int k = 5;
    
    cout<<"Number of subarrays with sum equal to "<<k<<" = "<<subArraySum(arr,k)<<endl;
    
  return 0;
}

ഔട്ട്പുട്ട്

Number of subarrays with sum equal to 5 = 7

ജാവ പ്രോഗ്രാം ഫോർ സബറേ തുക k ന് തുല്യമാണ്

import java.io.*;
import java.util.*;

class tutorialCup 
{
    // function to find number of subarrays with sum = k
    static int subArraySum(ArrayList <Integer> arr,int k)
    {
        int n = arr.size();
        int count = 0;
        
        // generate all the subarrays
        // a given subarray within range [start,end]
        // is chosen
        for(int start=0;start<n;start++)
        {
            for(int end=start+1;end<=n;end++)
            {
                int sum = 0;
                
                // find sum of the elements in range[start,end]
                for(int i=start;i<end;i++)
                sum += arr.get(i);
                
                // if the given sum equals to k 
                // then increment the required count value
                if(sum == k)
                count++;
                
            }
        }
        return count;
    }
    
    // main program to implement above functions    
    public static void main (String[] args) 
    {
        ArrayList <Integer> arr = new ArrayList<Integer>(Arrays.asList(5,0,5,10,3,2,-15,4));
        int k = 5;
        
        System.out.println("Number of subarrays with sum equal to "+k+" = "+subArraySum(arr,k));
    }
}

ഔട്ട്പുട്ട്

Number of subarrays with sum equal to 5 = 7

സങ്കീർണ്ണത വിശകലനം

  • സമയ സങ്കീർണ്ണത: T (n) = O (n3)
  • ബഹിരാകാശ സങ്കീർണ്ണത: A (n) = O (1)

സഞ്ചിത തുക ഉപയോഗിക്കുന്നു

സമീപനം

എല്ലാ സബ്‌റേകളും സൃഷ്‌ടിച്ച് അവയുടെ തുക കണക്കാക്കുന്നതിന് പകരം. ഞങ്ങൾ ഒരു ക്യുമുലേറ്റീവ് സം അറേ ഉപയോഗിക്കുന്നു തുക [] അതിൽ സംഖ്യ [i] സൂചിക (i-1) വരെ എല്ലാ അറേ ഘടകങ്ങളുടെയും ആകെത്തുക സംഭരിക്കുന്നു. രണ്ട് സൂചികകൾക്കിടയിൽ (i, j) കിടക്കുന്ന മൂലകങ്ങളുടെ ആകെത്തുക കണക്കാക്കുന്നതിന്, തുക നേരിട്ട് ലഭിക്കുന്നതിന് രണ്ട് സൂചികകളുമായി ബന്ധപ്പെട്ട സഞ്ചിത തുക (തുക [i] - തുക [j-1]) കുറയ്ക്കാം.

സബാരെയുടെ അൽ‌ഗോരിതം k ന് തുല്യമാണ്

  1. ഒരു ക്യുമുലേറ്റീവ് സം അറേ സൃഷ്ടിക്കുക തുക [] നീളം n + 1 (ഇൻപുട്ട് അറേയുടെ n = വലുപ്പം arr []).
  2. നീക്കിവയ്ക്കുക തുക [0] = 0, പൂജ്യ ഘടകങ്ങളുടെ ആകെത്തുക.
  3. ആവർത്തിക്കുക arr [] നിയോഗിക്കുക തുക [i] = ശ്രേണിയിലെ മൂലകങ്ങളുടെ ആകെത്തുക [0, i-1].
  4. [0, n-1] പരിധിയിൽ ഒരു ബാഹ്യ ലൂപ്പ് പ്രവർത്തിപ്പിക്കുക. ലൂപ്പ് വേരിയബിൾ ആണ് ആരംഭിക്കുക.
  5. പരിധിയിൽ ഒരു ആന്തരിക ലൂപ്പ് പ്രവർത്തിപ്പിക്കുക [ആരംഭിക്കുക + 1, n]. ലൂപ്പ് വേരിയബിൾ ആണ് അവസാനം.
  6. ശ്രേണിയിലെ ഘടകങ്ങളുടെ ആകെത്തുക [ആരംഭം, അവസാനം] = തുക [അവസാനം] - തുക [ആരംഭം].
  7. ഈ തുക k ന് തുല്യമാണെങ്കിൽ, വർദ്ധിപ്പിക്കുക എണ്ണുക വേരിയബിൾ.

മുകളിലുള്ള അൽ‌ഗോരിതം ചുവടെ ചിത്രീകരിച്ചിരിക്കുന്നു:

സബ്‌റേ തുക k ന് തുല്യമാണ്

നമ്മൾ നിരീക്ഷിക്കുന്നതുപോലെ ഉണ്ട് 7 (എണ്ണം = 7) സബ്‌റേയുടെ ആകെത്തുക 5 (k = 5).

നടപ്പിലാക്കൽ

സി ++ പ്രോഗ്രാം ഫോർ സബാരേ തുക k ന് തുല്യമാണ്

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// function to find number of subarrays with sum = k
int subArraySum(vector <int> arr,int k)
{
    int n = arr.size();
    int count = 0;
    
    // create an array to store cumulative sum
    // initialize the array as 0
    int *sum = new int[n+1];
    memset(sum,0,sizeof(sum));
    
    // find the cumulative sum for each index of arr[]
    for(int i=1;i<=n;i++)
    sum[i] =sum[i-1]+arr[i-1];
    
    // generate all the subarrays
    // a given subarray within range [start,end]
    // is chosen
    for(int start=0;start<n;start++)
    {
        for(int end=start+1;end<=n;end++)
        {
            // find the sum in range[start,end]
            // using sum array (which is used to store cumulative sum)
            // if sum equals to given k
            // then increase the count
            if(sum[end] - sum[start] == k)
            count++;
        }
    }
    return count;
}

// main program to implement above functions
int main() 
{
    vector <int> arr = {5,0,5,10,3,2,-15,4};
    int k = 5;
    
    cout<<"Number of subarrays with sum equal to "<<k<<" = "<<subArraySum(arr,k)<<endl;
    
  return 0;
}

ഔട്ട്പുട്ട്

Number of subarrays with sum equal to 5 = 7

ജാവ പ്രോഗ്രാം ഫോർ സബറേ തുക k ന് തുല്യമാണ്

import java.io.*;
import java.util.*;

class tutorialCup 
{
    // function to find number of subarrays with sum = k
    static int subArraySum(ArrayList <Integer> arr,int k)
    {
        int n = arr.size();
        int count = 0;
        
        // create an array to store cumulative sum
        // initialize the array as 0
        int[] sum = new int[n+1];
        sum[0] = 0;
        
        // find the cumulative sum for each index of arr[]
        for(int i=1;i<=n;i++)
        sum[i] =sum[i-1]+arr.get(i-1);
        
        // generate all the subarrays
        // a given subarray within range [start,end]
        // is chosen
        for(int start=0;start<n;start++)
        {
            for(int end=start+1;end<=n;end++)
            {
                // find the sum in range[start,end]
                // using sum array (which is used to store cumulative sum)
                // if sum equals to given k
                // then increase the count
                if(sum[end] - sum[start] == k)
                count++;
            }
        }
        return count;
    }
    
    // main program to implement above functions    
    public static void main (String[] args) 
    {
        ArrayList <Integer> arr = new ArrayList<Integer>(Arrays.asList(5,0,5,10,3,2,-15,4));
        int k = 5;
        
        System.out.println("Number of subarrays with sum equal to "+k+" = "+subArraySum(arr,k));
    }
}

ഔട്ട്പുട്ട്

Number of subarrays with sum equal to 5 = 7

സങ്കീർണ്ണത വിശകലനം

  • സമയ സങ്കീർണ്ണത: T (n) = O (n2)
  • ബഹിരാകാശ സങ്കീർണ്ണത: A (n) = O (n)

അധിക ഇടം ഉപയോഗിക്കാതെ

സമീപനം

വ്യത്യസ്‌തമായി പരിഗണിക്കുമ്പോൾ എവിടെയായിരുന്നാലും തുക ഞങ്ങൾക്ക് നേരിട്ട് കണ്ടെത്താനാകും പോയിന്റുകൾ. ഞങ്ങൾക്ക് ഒരു പ്രത്യേകത തിരഞ്ഞെടുക്കാം തുടക്കം പോയിന്റ് (ലൂപ്പ് ഓവർ [0 മുതൽ n-1] വരെ) ഒരു ആന്തരിക ലൂപ്പിൽ എല്ലാ ഘടകങ്ങളും വലതുവശത്തേക്ക് ആവർത്തിക്കുക (ലൂപ്പ് ഓവർ [n-1 മുതൽ ആരംഭിക്കുക). ആന്തരിക ലൂപ്പിൽ ആവർത്തിക്കുമ്പോൾ ഞങ്ങൾ ഘടകങ്ങൾ ചേർക്കുന്നത് തുടരുന്നു തുക. എപ്പോഴെങ്കിലും തുക ആവശ്യമുള്ളതിന് തുല്യമാണ് k മൂല്യം, ഞങ്ങൾ എണ്ണം വർദ്ധിപ്പിക്കുന്നു. തന്നിരിക്കുന്നതിന്റെ വലതുവശത്തുള്ള എല്ലാ ഘടകങ്ങളെയും ആവർത്തിക്കുമ്പോൾ ഞങ്ങൾ അങ്ങനെ ചെയ്യുന്നു തുടക്കം സാധ്യമായ എല്ലാത്തിനും സൂചിക തുടക്കം സൂചിക മൂല്യം.

അൽഗോരിതം

  1. [0, n-1] പരിധിയിൽ ഒരു ബാഹ്യ ലൂപ്പ് പ്രവർത്തിപ്പിക്കുക. ലൂപ്പ് വേരിയബിൾ ആണ് ആരംഭിക്കുക.
  2. ഒരു വേരിയബിൾ സൃഷ്ടിക്കുക തുക ആന്തരിക ലൂപ്പിൽ മൂലകങ്ങളുടെ ആകെത്തുക സംഭരിക്കാനും അത് 0 ഉപയോഗിച്ച് സമാരംഭിക്കാനും.
  3. പരിധിയിൽ ഒരു ആന്തരിക ലൂപ്പ് പ്രവർത്തിപ്പിക്കുക [ആരംഭിക്കുക, n-1]. ലൂപ്പ് വേരിയബിൾ ആണ് അവസാനം.
  4. ആന്തരിക ലൂപ്പിൽ ആവർത്തനം ചെയ്യുമ്പോൾ കണ്ടെത്തുക തുക ന്റെ ഓരോ മൂല്യവും വരെയുള്ള ഘടകങ്ങളുടെ അവസാനം.
  5. മൂല്യം ഉണ്ടെങ്കിൽ ആന്തരിക ലൂപ്പിൽ ആവർത്തിക്കുമ്പോൾ തുക നൽകിയ k ന് തുല്യമായി മാറുന്നു, അതിന്റെ മൂല്യം വർദ്ധിപ്പിക്കുക എണ്ണം.
  6. അടുത്ത ആവർത്തന പുനർനിയമിക്കലിനായി തുക 0 ആയി.

നടപ്പിലാക്കൽ

സി ++ പ്രോഗ്രാം ഫോർ സബാരേ തുക k ന് തുല്യമാണ്

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// function to find number of subarrays with sum = k
int subArraySum(vector <int> arr,int k)
{
    int n = arr.size();
    int count = 0;
    
    // start with each element of arr
    for (int start = 0;start < n; start++) 
    {
        int sum=0;
        // find sum of elements until end
        for (int end = start;end < n; end++) 
        {
            sum += arr[end];
            // if sum equals to given k
            // increment the count
            if (sum == k)
                count++;
        }
    }
    return count;
}

// main program to implement above functions
int main() 
{
    vector <int> arr = {5,0,5,10,3,2,-15,4};
    int k = 5;
    
    cout<<"Number of subarrays with sum equal to "<<k<<" = "<<subArraySum(arr,k)<<endl;
    
  return 0;
}

ഔട്ട്പുട്ട്

Number of subarrays with sum equal to 5 = 7

ജാവ പ്രോഗ്രാം ഫോർ സബറേ തുക k ന് തുല്യമാണ്

import java.io.*;
import java.util.*;

class tutorialCup 
{
    // function to find number of subarrays with sum = k
    static int subArraySum(ArrayList <Integer> arr,int k)
    {
        int n = arr.size();
        int count = 0;
        
        // start with each element of arr
        for (int start = 0;start < n; start++) 
        {
            int sum=0;
            // find sum of elements until end
            for (int end = start;end < n; end++) 
            {
                sum += arr.get(end);
                // if sum equals to given k
                // increment the count
                if (sum == k)
                    count++;
            }
        }
        return count;
    }
    
    // main program to implement above functions    
    public static void main (String[] args) 
    {
        ArrayList <Integer> arr = new ArrayList<Integer>(Arrays.asList(5,0,5,10,3,2,-15,4));
        int k = 5;
        
        System.out.println("Number of subarrays with sum equal to "+k+" = "+subArraySum(arr,k));
    }
}

ഔട്ട്പുട്ട്

Number of subarrays with sum equal to 5 = 7

സമയ സങ്കീർണ്ണത

  • സമയ സങ്കീർണ്ണത: T (n) = O (n2)
  • ബഹിരാകാശ സങ്കീർണ്ണത: A (n) = O (1)

ഹാഷ് മാപ്പ് ഡാറ്റ ഘടന ഉപയോഗിക്കുന്നു

സമീപനം

ഞങ്ങൾ‌ ഇപ്പോൾ‌ മനസ്സിലാക്കുന്നതുപോലെ, രണ്ട് സൂചികകൾ‌ വരെ സഞ്ചിത സംഖ്യയാണെങ്കിൽ‌, പറയുക i ഒപ്പം j എന്നതിന്റെ വ്യത്യാസത്തിലാണ് k. അതായത് എങ്കിൽ sum [i] umsum [j] = k, തുടർന്ന് സൂചികകൾക്കിടയിൽ കിടക്കുന്ന മൂലകങ്ങളുടെ ആകെത്തുക i ഉം j ഉം k ആണ്.

ഞങ്ങൾ ഒരു ഹാഷ്മാപ്പ് സൃഷ്ടിക്കുന്നു ഒരു പ്രത്യേക സംഖ്യയുടെ മൂല്യം എത്രതവണ സംഭവിക്കുന്നു എന്നതിനൊപ്പം സാധ്യമായ എല്ലാ സൂചികകളിലേക്കും സഞ്ചിത തുക സംഭരിക്കാൻ ഇത് ഉപയോഗിക്കുന്നു. ആവശ്യമായ ഡാറ്റ ഫോം മാപ്പിൽ മാപ്പിൽ സംഭരിച്ചിരിക്കുന്നു (ആകെ -> തുടർച്ചയായ സബ്‌റേയിൽ ആകെ സംഭവങ്ങളുടെ എണ്ണം). ഞങ്ങൾ അറേയിലൂടെ സഞ്ചരിക്കുന്നു arr [] സഞ്ചിത തുക കണ്ടെത്തുന്നത് തുടരുക, അത് വേരിയബിളിൽ സംഭരിക്കുക തുക. ഓരോ തവണയും ഞങ്ങൾ ഒരു പുതിയ തുക നേരിടുമ്പോൾ, ആ തുകയ്‌ക്ക് അനുയോജ്യമായ ഹാഷ്‌മാപ്പിൽ ഞങ്ങൾ ഒരു പുതിയ എൻ‌ട്രി നടത്തുന്നു.

അതേ തുക വീണ്ടും സംഭവിക്കുകയാണെങ്കിൽ, ഹാഷ്‌മാപ്പിലെ ആ തുകയ്‌ക്ക് സമാനമായ എണ്ണം (ഹാഷ്‌മാപ്പിലെ പ്രത്യേക തുകയുടെ മൂല്യം) ഞങ്ങൾ വർദ്ധിപ്പിക്കുന്നു. കൂടാതെ, നേരിട്ട ഓരോ തുകയ്ക്കും, എത്ര തവണയാണെന്നും ഞങ്ങൾ നിർണ്ണയിക്കുന്നു ഇതിനകം സംഭവിച്ചു (കീ മൂല്യമായി), ഇത് അടിസ്ഥാനപരമായി സംഖ്യ = k ഉള്ള ഒരു സബ്‌റേ നിലവിലെ സൂചിക വരെ എത്ര തവണ സംഭവിച്ചുവെന്ന് നിർണ്ണയിക്കുന്നു. അതിനാൽ, ഞങ്ങൾ വർദ്ധിപ്പിക്കണം എണ്ണുക അതേ അളവിൽ. ന്റെ ട്രാവെർസൽ മൂല്യത്തിന്റെ അവസാനം എണ്ണുക ഞങ്ങളുടെ ആവശ്യമായ ഫലമാണ്.

അൽഗോരിതം

  1. ഒരു ഹാഷ്‌മാപ്പ് സൃഷ്‌ടിക്കുക മാപ്പ്
  2. തന്നിരിക്കുന്ന അറേയിലൂടെ സഞ്ചരിക്കുക.
  3. ഓരോ ഘട്ടത്തിലും, സൂചിക i വരെ എല്ലാ ഘടകങ്ങളും (സഞ്ചിത തുക കണ്ടെത്തുക) സംഗ്രഹിക്കുക, അതിൽ സംഭരിക്കുക തുക.
  4. ഉണ്ടോയെന്ന് പരിശോധിക്കുക തുക - k മാപ്പിലെ കീയായി നിലവിലുണ്ട്, ഇത് k- ന് തുല്യമായതോ അല്ലാത്തതോ ആയ i- ൽ അവസാനിക്കുന്ന ഒരു സബ്‌റേ ഉണ്ടോ എന്ന് പരിശോധിക്കുന്നതിനാണ് ഇത് ചെയ്യുന്നത്.
  5. if തുക - k നിലവിലുണ്ട് (സം = k ഉപയോഗിച്ച് i ൽ അവസാനിക്കുന്ന സബ്‌റേ നിലവിലുണ്ട്), ഇതിനായി മാപ്പുചെയ്‌ത മൂല്യം ഉപയോഗിച്ച് എണ്ണത്തിന്റെ മൂല്യം വർദ്ധിപ്പിക്കുക തുക - k മാപ്പിൽ.
  6. എണ്ണം കൂട്ടാനും കൂട്ടാനും മറക്കരുത് തുക (സഞ്ചിത തുക) മാപ്പിലേക്ക് ഓരോ ഘട്ടത്തിലും ലഭിച്ചു.

മുകളിലുള്ള അൽ‌ഗോരിതം ചുവടെ ചിത്രീകരിച്ചിരിക്കുന്നു:

നടപ്പിലാക്കൽ

സി ++ പ്രോഗ്രാം ഫോർ സബാരേ തുക k ന് തുല്യമാണ്

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// function to find number of subarrays with sum = k
int subArraySum(vector <int> arr,int k)
{
    int n = arr.size();
    int count = 0,sum = 0;
    
    // create a hashmap
    unordered_map <int,int> Map;
    
    // when no element is chosen, value of sum is 0
    Map[0] = 1;
    
    for (int i = 0; i < n; i++) 
    {
        // in each step, find the cumulative sum
        sum += arr[i];
        // check if sum-k exists in map 
        // if exists the increment count by
        // mapped value for sum-k
        if (Map.find(sum-k) != Map.end())
            count += Map[sum-k];
        
        // add the cumulative sum obtained until now into the map
        Map[sum] = Map[sum] + 1;
    }
    return count;
}

// main program to implement above functions
int main() 
{
    vector <int> arr = {5,0,5,10,3,2,-15,4};
    int k = 5;
    
    cout<<"Number of subarrays with sum equal to "<<k<<" = "<<subArraySum(arr,k)<<endl;
    
  return 0;
}

ഔട്ട്പുട്ട്

Number of subarrays with sum equal to 5 = 7

ജാവ പ്രോഗ്രാം ഫോർ സബറേ തുക k ന് തുല്യമാണ്

import java.io.*;
import java.util.*;

class tutorialCup 
{
    // function to find number of subarrays with sum = k
    static int subArraySum(ArrayList <Integer> arr,int k)
    {
        int n = arr.size();
        int count = 0,sum = 0;
        
        // create a hashmap
        HashMap <Integer, Integer> map = new HashMap <>();
        
        // when no element is chosen, value of sum is 0
        map.put(0, 1);
        
        for (int i = 0; i < n; i++) 
        {
            // in each step, find the cumulative sum
            sum += arr.get(i);
            
            // check if sum-k exists in map 
            // if exists the increment count by
            // mapped value for sum-k
            if (map.containsKey(sum - k))
                count += map.get(sum - k);
            
            // add the cumulative sum obtained until now into the map
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return count;
    }
    
    // main program to implement above functions    
    public static void main (String[] args) 
    {
        ArrayList <Integer> arr = new ArrayList<Integer>(Arrays.asList(5,0,5,10,3,2,-15,4));
        int k = 5;
        
        System.out.println("Number of subarrays with sum equal to "+k+" = "+subArraySum(arr,k));
    }
}

ഔട്ട്പുട്ട്

Number of subarrays with sum equal to 5 = 7

സങ്കീർണ്ണത വിശകലനം

  • സമയ സങ്കീർണ്ണത: T (n) = O (n)
  • ബഹിരാകാശ സങ്കീർണ്ണത: A (n) = O (n)

അവലംബം