የሰርቤሪ ድምር እኩልነት k


የችግር ደረጃ መካከለኛ
ውስጥ በተደጋጋሚ ተጠየቀ የ Adobe አማዞን አሜሪካን ኤክስፕረስ ብሉምበርግ eBay ፌስቡክ ጎልድማን ሳክስ google የ Microsoft ቴሊዮ ያሁ
ሰልፍ ሃሽ

ኢንቲጀር ተሰጠ ደርድር እና ኢንቲጀር ኪ. የእነሱ ንጥረ ነገሮች ድምር ከ 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)።

አፈጻጸም

የ C ++ ፕሮግራም ለሱብሪይ ድምር እኩል ይሆናል 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)

የተጠራቀመ ድምርን በመጠቀም

ቀረበ

ሁሉንም subarrays ከማመንጨት እና ድምርአቸውን ከማስላት ይልቅ። የተጠራቀመ ድምር ድርድርን እንጠቀማለን ድምር [] ድምር [i] እስከ ኢንዴክስ (i-1) ድረስ ሁሉንም የድርጅት አባሎች ድምር ያከማቻል። ከዚያም በሁለት ማውጫዎች (i እና j) መካከል የተኙትን ንጥረ ነገሮች ድምር ለማስላት ድምርን በቀጥታ ለማግኘት ከሁለቱ ኢንዴክሶች ጋር የሚዛመደውን ድምር (ድምር [i] - ድምር [j-1]) መቀነስ እንችላለን ፡፡

ስልተ-ቀመር ለ Subarray ድምር እኩል ይሆናል k

  1. ድምር ድምር ድርድርን ይፍጠሩ ድምር [] ርዝመት n + 1 (n = የግብዓት ድርድር መጠን።) arr []).
  2. ትእዛዝ ሰጠ ድምር [0] = 0 ፣ የዜሮ አባሎች ድምር።
  3. ከመጠን በላይ ንዴት arr [] እና መመደብ ድምር [እኔ] = በክልል ውስጥ ያሉ ንጥረ ነገሮች ድምር [0 ፣ i-1]።
  4. በክልል [0 ፣ n-1] ውስጥ የውጭ ዑደትን ያሂዱ። የሉፕ ተለዋዋጭ ነው ጀምር.
  5. በክልል ውስጥ ውስጠ-ክበብን ያሂዱ [ጅምር + 1 ፣ n]። የሉፕ ተለዋዋጭ ነው መጨረሻ
  6. በክልል [ጅምር ፣ መጨረሻ] = ድምር [መጨረሻ] - ድምር [ጅምር] ውስጥ ያሉ ንጥረ ነገሮች ድምር።
  7. ይህ ድምር ከ k ጋር እኩል ከሆነ ፣ ከዚያ ይጨምሩ ተጐዳሁ: ተለዋዋጭ.

ከላይ ያለው ስልተ ቀመር ከዚህ በታች ቀርቧል

ንዑስ ክፍል ድምር እኩል ይሆናል k

እንደምናስተውለው አሉ 7 (ቆጠራ = 7) ንዑስ ንዑስ ቡድን ድምር የሚገኝባቸው አጋጣሚዎች 5 (k = 5) ፡፡

አፈጻጸም

የ C ++ ፕሮግራም ለሱብሪይ ድምር እኩል ይሆናል 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] በላይ ቀለበት) እና ሁሉንም ነገሮች በትክክለኛው ላይ ያስተካክሉ (loop over [n-1 to start)) በውስጠኛው ዑደት ውስጥ። በውስጠኛው ዑደት ውስጥ በሚሠራበት ጊዜ ንጥረ ነገሮችን ማከል እንቀጥላለን ድምር. መቼም ድምር ከሚያስፈልገው ጋር እኩል ነው k እሴት ፣ እኛ እንጨምራለን። ከተሰጠ በስተቀኝ በኩል ያሉትን ሁሉንም ንጥረ ነገሮች እየለዋወጥን እናደርጋለን መጀመሪያ ለሁሉም የሚቻል መረጃ ጠቋሚ መጀመሪያ የመረጃ ጠቋሚ እሴት።

አልጎሪዝም

  1. በክልል [0 ፣ n-1] ውስጥ የውጭ ዑደትን ያሂዱ። የሉፕ ተለዋዋጭ ነው ጀምር.
  2. ተለዋዋጭ ይፍጠሩ ድምር በውስጣዊ ዑደት ውስጥ ያሉትን ንጥረ ነገሮች ድምር ለማከማቸት እና በ 0 ለመጀመር ፡፡
  3. በክልል ውስጥ የውስጥ ዑደትን ያሂዱ [ጅምር ፣ n-1]። የሉፕ ተለዋዋጭ ነው መጨረሻ
  4. በውስጠኛው ሉፕ ግኝት ውስጥ ኢታርት እያለ ድምር እስከ እያንዳንዱ እሴት ድረስ ያሉ ንጥረ ነገሮች መጨረሻ
  5. በውስጠኛው ዑደት ውስጥ እየደመመ እያለ ፣ ዋጋ ከሆነ ድምር ከተሰጠ k ጋር እኩል ይሆናል ፣ የ እሴት ይጨምራል ቆጠረ።
  6. ለቀጣይ ድግግሞሽ እንደገና ይመደቡ ድምር እንደ 0 ፡፡

አፈጻጸም

የ C ++ ፕሮግራም ለሱብሪይ ድምር እኩል ይሆናል 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)

የሃሽ ካርታ የውሂብ መዋቅርን በመጠቀም

ቀረበ

አሁን እንደተረዳን ድምር እስከ ሁለት ማውጫዎች ከሆነ ይበሉ ij የሚለው ላይ ነው k. ማለትም ከሆነ ድምር [i] −sum [j] = ኪ፣ ከዚያ በመረጃ ጠቋሚዎች መካከል የተኙ ንጥረ ነገሮች ድምር እኔ እና ጄ ኬ ነው.

ሃሽማፕ እንፈጥራለን የተጠቃለለ ድምርን እስከሚቻልባቸው ሁሉንም ኢንዴክሶች ለማከማቸት የሚያገለግል ሲሆን ይህም የአንድ የተወሰነ ድምር ዋጋ ከሚከሰትባቸው ጊዜያት ብዛት ጋር ነው ፡፡ አስፈላጊው መረጃ በቅጽ ካርታ ውስጥ በካርታ ውስጥ ተከማችቷል (ድምር -> በተዛማጅ ንዑስ ክፍል ውስጥ የድምር ክስተቶች ብዛት)። በድርድሩ ላይ እናልፋለን arr [] እና የተጠራቀመውን ድምር መፈለግዎን ይቀጥሉ እና በተለዋጭ ውስጥ ያከማቹ ድምር አዲስ ድምር ባጋጠመን ቁጥር ከዚያ ገንዘብ ጋር በሚመሳሰል ሃሽማፕ ውስጥ አዲስ ግባ እናደርጋለን ፡፡

ተመሳሳዩ ድምር እንደገና ከተከሰተ በሃሽማው ውስጥ ካለው ከዚህ ጋር የሚስማማውን ቆጠራ (ለዚያ ልዩ ሂሳብ ዋጋ) እንጨምረዋለን። በተጨማሪም ፣ ለገጠሙን እያንዳንዱ ድምር እኛ የምንወስናቸውን ጊዜያት ብዛት እንወስናለን ቀድሞውኑ ተገኝቷል (እንደ ቁልፍ እሴት) ፣ በመሠረቱ የአሁኑን መረጃ ጠቋሚ እስከ ድምር = k ንዑስ ቡድንን የሚወስንበትን ጊዜ የሚወስን ስለሆነ ስለዚህ እኛ መጨመር አለብን ተጐዳሁ: በተመሳሳይ መጠን ፡፡ በትራንስፖርት እሴት መጨረሻ ላይ ተጐዳሁ: የምንፈልገው ውጤት ነው ፡፡

አልጎሪዝም

  1. ሃሽፕ ይፍጠሩ ካርታ
  2. የተሰጠውን ድርድር ያቋርጡ።
  3. በእያንዳንዱ ደረጃ ላይ ሁሉንም ንጥረ ነገሮች (ድምር ድምርን ያግኙ) እስከ ኢንዴክስ i ድረስ ይደምሩ ፣ ያከማቹ ድምር
  4. ከሆነ ያረጋግጡ ድምር - k በካርታው ውስጥ ቁልፍ ሆኖ ይገኛል ፣ ይህ ድምር ከ k ጋር ወይም ከሌላው ጋር የተጠናቀቀ ንዑስ ቡድን መኖሩን ለመፈተሽ የተደረገ ነው ፡፡
  5. if ድምር - k አሁን ይገኛል (ንዑስ ረድፍ በ i በ sum = k አለ) ፣ የቁጥር ዋጋን በካርታ እሴት ይጨምሩ ድምር - k በካርታው ውስጥ.
  6. ቁጥሩን ማከል / መጨመርን አይርሱ ድምር በእያንዳንዱ ደረጃ ወደ ካርታው የተገኘ (ድምር ድምር)።

ከላይ ያለው ስልተ ቀመር ከዚህ በታች ቀርቧል

አፈጻጸም

የ C ++ ፕሮግራም ለሱብሪይ ድምር እኩል ይሆናል 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)

ማጣቀሻዎች