Subarray Sum-ге тең  


Күрделілік дәрежесі орта
Жиі кіреді Adobe Amazon American Express Bloomberg еВау Facebook Голдман Сакс Google Microsoft Twilio Yahoo
Array Hash

Бүтін сан берілген массив және бүтін 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. Brute Force / Naive
  2. Жинақталған қосынды қолдану
  3. қосымша орын пайдаланбай
  4. Hash Map деректер құрылымын пайдалану

Brute Force / Naive  

жақындау

Идеясы берілген жиымның барлық ішкі жиынын құру және ішкі массив элементтерінің қосындысы k-ге тең екендігін тексеру. Егер ішкі массив элементтерінің қосындысы берілген k-ге тең болса, онда мәнін көбейтіңіз санау қажетті нәтижені сақтау үшін қолданылады.

Алгоритм

  1. Сыртқы циклды [0-ден n-1] аралығында іске қосыңыз. Цикл айнымалысы бастау.
  2. Ішкі циклды [start + 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

Subarray үшін Java бағдарламасы 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 (n)3)
  • Кеңістіктің күрделілігі: A (n) = O (1)

Жинақталған қосынды қолдану  

жақындау

Барлық ішкі массивтерді құрудың және олардың қосындысын есептеудің орнына. Біз жиынтық қосынды жиымын қолданамыз қосынды [] мұндағы sum [i] барлық массив элементтерінің қосындысын (i-1) индекске дейін сақтайды. Содан кейін, екі индекстің арасында орналасқан элементтердің қосындысын есептеу үшін (i және j), қосындысын тікелей алу үшін екі индекске сәйкес жинақталған қосындысын (қосынды [i] - қосынды [j-1]) алып тастай аламыз.

Сондай-ақ, қараңыз
Жиым басқа массивтің ішкі жиыны екенін табыңыз

Қосымшаға арналған алгоритм 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 (count = 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

Subarray үшін Java бағдарламасы 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 (n)2)
  • Кеңістіктің күрделілігі: A (n) = O (n)
Сондай-ақ, қараңыз
Бір-біріне сәйкес келмейтін 3 ішкі массивтің максималды қосындысы

Қосымша орынды пайдаланбай  

жақындау

Қосымшаны басқаша қарастырған кезде тікелей таба аламыз балл. Біз белгілі бір түрін таңдай аламыз бастау нүкте ([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

Subarray үшін Java бағдарламасы 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 (n)2)
  • Кеңістіктің күрделілігі: A (n) = O (1)
Сондай-ақ, қараңыз
Плюс кодының бір шешімі

Hash Map деректер құрылымын пайдалану  

жақындау

Біздің түсінгеніміздей, егер екі индекстің жиынтық сомасы болса, айталық i және j айырмашылықта болады k. яғни егер қосынды [i] −sum [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

Subarray үшін Java бағдарламасы 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)
Сондай-ақ, қараңыз
Массивтің шешім кодынан Lucky бүтін санды табыңыз

Әдебиеттер тізімі