Suma podtablicy równa się k

Poziom trudności Średni
Często zadawane pytania Adobe Amazonka American Express Bloomberg eBay Facebook Goldman Sachs Google Microsoft Twilio Yahoo
Szyk Haszyszodwiedzajacy 98

Pytania do rozmowy kwalifikacyjnej na temat projektowania systemu może być tak nieograniczona, że ​​trudno jest określić właściwy sposób przygotowania. Teraz jestem w stanie złamać rundy projektowe Amazon, Microsoft i Adobe po zakupie ta książka. Codziennie poprawiaj jeden pytanie projektowe i obiecuję, że możesz złamać cały projekt.

Biorąc pod uwagę liczbę całkowitą szyk i liczbę całkowitą k. Znajdź całkowitą liczbę ciągłych podtablic z danej tablicy, których suma elementów jest równa k.

Przykład

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

Objaśnienie: weź pod uwagę przykład-1 podany powyżej, poniższy obrazek wyróżnia wszystkie podtablice o zadanej sumie k (= 5).

Suma podtablicy równa się kszpilka

Rodzaje rozwiązań

  1. Brute Force / Naiwny
  2. Korzystanie z sumy skumulowanej
  3. bez użycia dodatkowej przestrzeni
  4. Korzystanie ze struktury danych Hash Map

Brute Force / Naiwny

Podejście

Chodzi o to, aby wygenerować wszystkie podtablice z podanej tablicy i sprawdzić, czy suma elementów podtablicy jest równa zadanemu k. Jeśli suma elementów podtablicy jest równa zadanemu k, to zwiększ wartość liczyć służy do przechowywania wymaganego wyniku.

Algorytm

  1. Uruchom zewnętrzną pętlę od zakresu [0 do n-1]. Zmienna pętli to początek.
  2. Uruchom pętlę wewnętrzną z zakresu [start + 1, n]. Zmienna pętli to koniec.
  3. Uruchom pętlę zagnieżdżoną w powyższej pętli z zakresu [początek, koniec-1] i oblicz suma w tym zakresie.
  4. Jeśli suma jest równa danemu k, zwiększ wartość liczyć.

Powyższy algorytm przedstawiono poniżej:

Suma podtablicy równa się kszpilka Suma podtablicy równa się kszpilka Suma podtablicy równa się kszpilka Suma podtablicy równa się kszpilka Suma podtablicy równa się kszpilka Suma podtablicy równa się kszpilka

Na powyższych obrazach widzimy, że w sumie jest 7 podtablic (podświetlonych w czerwony), które mają podaną sumę (k = 5).

Realizacja

Program w C ++ dla Subarray suma równa się 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;
}

Wydajność

Number of subarrays with sum equal to 5 = 7

Suma programu Java dla tablicy podrzędnej wynosi 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));
    }
}

Wydajność

Number of subarrays with sum equal to 5 = 7

Analiza złożoności

  • Złożoność czasowa: T (n) = O (n3)
  • Złożoność przestrzeni: A (n) = O (1)

Korzystanie z sumy skumulowanej

Podejście

Zamiast generować wszystkie podtablice i obliczać ich sumę. Używamy skumulowanej tablicy sum suma[] gdzie sum [i] przechowuje sumę wszystkich elementów tablicy do indeksu (i-1). Następnie, aby obliczyć sumę elementów leżących między dwoma wskaźnikami (i i j), możemy odjąć skumulowaną sumę (suma [i] - suma [j-1]) odpowiadającą dwóm indeksom, aby otrzymać sumę bezpośrednio.

Algorytm dla sumy podtablicy wynosi k

  1. utwórz tablicę sum skumulowanych suma[] o długości n + 1 (n = rozmiar tablicy wejściowej arr []).
  2. przydzielać suma [0] = 0, suma zerowych elementów.
  3. Powtarzaj arr [] i przypisz suma [i] = suma elementów w zakresie [0, i-1].
  4. Uruchom zewnętrzną pętlę w zakresie [0, n-1]. Zmienna pętli to początek.
  5. Uruchom wewnętrzną pętlę w zakresie [start + 1, n]. Zmienna pętli to koniec.
  6. Suma elementów w zakresie [początek, koniec] = suma [koniec] - suma [początek].
  7. Jeśli ta suma jest równa k, zwiększ wartość liczyć zmienna.

Powyższy algorytm przedstawiono poniżej:

szpilka Suma podtablicy równa się kszpilka szpilka

Jak obserwujemy, są 7 (count = 7) instancje, w których suma podtablicy wynosi 5 (k = 5).

Realizacja

Program w C ++ dla Subarray suma równa się 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;
}

Wydajność

Number of subarrays with sum equal to 5 = 7

Suma programu Java dla tablicy podrzędnej wynosi 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));
    }
}

Wydajność

Number of subarrays with sum equal to 5 = 7

Analiza złożoności

  • Złożoność czasowa: T (n) = O (n2)
  • Złożoność przestrzeni: A (n) = O (n)

Bez użycia dodatkowej przestrzeni

Podejście

Możemy bezpośrednio znaleźć sumę w ruchu, rozważając różne punktów. możemy wybrać konkretny początek punkt (pętla nad [0 do n-1]) i iteruj po wszystkich elementach po prawej stronie (pętla po [początek do n-1]) w wewnętrznej pętli. Dodajemy elementy podczas iteracji w wewnętrznej pętli do suma. Zawsze, gdy suma równa się wymaganemu k wartość, zwiększamy liczbę. Robimy to podczas iteracji po wszystkich elementach na prawo od danego początek indeks dla każdego możliwego początek wartość indeksu.

Algorytm

  1. Uruchom zewnętrzną pętlę w zakresie [0, n-1]. Zmienna pętli to początek.
  2. utwórz zmienną suma aby przechowywać sumę elementów w pętli wewnętrznej i zainicjować ją wartością 0.
  3. Uruchom wewnętrzną pętlę w zakresie [start, n-1]. Zmienna pętli to koniec.
  4. Podczas iteracji w wewnętrznej pętli znajdź suma elementów do każdej wartości koniec.
  5. Podczas iteracji w pętli wewnętrznej, jeśli wartość suma staje się równe zadanemu k, zwiększ wartość liczyć.
  6. Do następnej iteracji przypisać ponownie suma jako 0.

Realizacja

Program w C ++ dla Subarray suma równa się 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;
}

Wydajność

Number of subarrays with sum equal to 5 = 7

Suma programu Java dla tablicy podrzędnej wynosi 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));
    }
}

Wydajność

Number of subarrays with sum equal to 5 = 7

Złożoność czasowa

  • Złożoność czasowa: T (n) = O (n2)
  • Złożoność przestrzeni: A (n) = O (1)

Korzystanie ze struktury danych Hash Map

Podejście

Jak teraz rozumiemy, że jeśli skumulowana suma do dwóch wskaźników, powiedzmy i i j jest na różnicy k. tj. jeśli suma [i] −sum [j] = k, to suma elementów leżących między indeksami i i j to k.

Tworzymy hashmap który jest używany do przechowywania skumulowanej sumy wszystkich możliwych wskaźników wraz z liczbą wystąpień określonej wartości sumy. Wymagane dane są przechowywane w mapie w postaci mapy (suma -> liczba wystąpień sumy w ciągłej podtablicy). Przechodzimy przez tablicę arr [] i kontynuuj znajdowanie skumulowanej sumy i przechowuj ją w zmiennej suma. Za każdym razem, gdy napotykamy nową sumę, dokonujemy nowego wpisu w tablicy haszy odpowiadającej tej sumie.

Jeśli ta sama suma wystąpi ponownie, zwiększamy liczbę (wartość tej konkretnej sumy w hasmapie) odpowiadającą tej sumie w hashmap. Ponadto dla każdej napotkanej sumy określamy również, ile razy wystąpiła już (jako wartość klucza), ponieważ zasadniczo określa, ile razy podtablica o sum = k wystąpiła do bieżącego indeksu, więc musimy zwiększyć wartość liczyć o tę samą kwotę. Pod koniec przemierzania wartość liczyć to nasz wymagany wynik.

Algorytm

  1. utwórz hashmap mapa
  2. Przejdź przez podaną tablicę.
  3. Na każdym kroku zsumuj wszystkie elementy (znajdź sumę skumulowaną) do indeksu i, zapisz go suma.
  4. sprawdź, czy suma - k jest obecny jako klucz na mapie, robi się to w celu sprawdzenia, czy istnieje podtablica kończąca się na i, której suma jest równa k, czy nie.
  5. if suma - k jest obecny (podtablica kończąca się na i z sumą = k istnieje), zwiększ wartość licznika o odwzorowaną wartość dla suma - k na mapie.
  6. nie zapomnij dodać / zwiększyć liczby suma (suma skumulowana) uzyskana w każdym kroku na mapie.

Powyższy algorytm przedstawiono poniżej:

szpilka

szpilka

Realizacja

Program w C ++ dla Subarray suma równa się 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;
}

Wydajność

Number of subarrays with sum equal to 5 = 7

Suma programu Java dla tablicy podrzędnej wynosi 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));
    }
}

Wydajność

Number of subarrays with sum equal to 5 = 7

Analiza złożoności

  • Złożoność czasowa: T (n) = O (n)
  • Złożoność przestrzeni: A (n) = O (n)

Referencje

Wywiady dotyczące projektowania systemu pękania
Translate »