ከተሰጠ ድምር ጋር ንዑስ ድርድርን ያግኙ (አሉታዊ ቁጥሮችን ያስተናግዳል)


የችግር ደረጃ መካከለኛ
ውስጥ በተደጋጋሚ ተጠየቀ አማዞን ኩፖንዱኒያ አቅርቦት GE የጤና InfoEdge የሞንፎርግ ቤተ ሙከራዎች
ሰልፍ ሃሽ የተንሸራታች መስኮት

ችግሩ “ከተሰጠ ድምር ጋር ንዑስ ድርድርን ይፈልጉ” (አሉታዊ አሃዞችን ያስተናግዳል) ፣ “አንድ” እንደተሰጠዎት ይናገራል ኢንቲጀር ደርድር፣ አሉታዊ ቁጥሮችን እንዲሁም “ድምር” የተባለ ቁጥር የያዘ። የችግሩ መግለጫ ንዑስ-ድርድርን ለማተም ይጠይቃል ፣ እሱም “ድምር” እስከሚባል የተሰጠ ቁጥር ይደመራል። ከአንድ በላይ ንዑስ ድርድር እንደ ውጤታችን የሚገኝ ከሆነ ፣ ማንኛቸውምንም ያትሙ።

ለምሳሌ

ከተሰጠ ድምር ጋር ንዑስ ድርድርን ያግኙ (አሉታዊ ቁጥሮችን ያስተናግዳል)

arr[] = {2,4,-2,3,1}
sum = 1
Sum found between index 2 to index 3
arr[] = {12,10,-20,30,1}
sum = 20
Sum found between index 1 to index 3
arr[] = {2,4,-2,3,1}
sum = -1
No such sub-array exists.

አልጎሪዝም

  1. ያውጅ ሀ ካርታ.
  2. አዘጋጅ currentSum 0 ነው.
  3. ድርድርን ያቋርጡ ፣ i <n እያለ,
    1. የወቅቱ የሱም እና የድርድር ንጥረ ነገር ዋጋን ጠቅልሎ ወደ የአሁኑ ሱም ያከማቻል።
    2. የአሁኑ ሱም ከድምሩ ጋር እኩል መሆኑን ያረጋግጡ።
      • እውነት ከሆነ ፣ ከዚያ ማውጫውን ከ 0 እስከ i ድረስ ያትሙ እና ይሰብሩ።
    3. ካርታው የአሁኑን ዋጋ ሱም-ድምር የያዘ መሆኑን ያረጋግጡ።
      • እውነት ከሆነ ከዚያ ማውጫዎቹን እንደ የካርታ የአሁኑ የሱም እሴት ለ i እና ለማቋረጥ ያትሙ።
    4. ከተሰጡት ማናቸውም ሁኔታዎች የማያሟላ ከሆነ ፣ በተጠቀሰው ድምር ምንም አላገኘንም ማለት ነው ፡፡

ማስረጃ

የተሰጠውን ድምር የሚያጠቃልል ንዑስ-ድርድርን ለማወቅ የሚጠይቅ የችግር መግለጫ ተሰጥቶናል እናም ከአንድ በላይ ንዑስ ድርድር ከተገኘ ከዚያ ማንኛውንም ማተም ያትሙ ፡፡ ልንጠቀምበት ነው ሃሽ ማፕcurrentSum እያንዳንዱን ንጥረ ነገር ከጨመረ በኋላ ምንም ሁኔታዎች ካላሟሉ እና መረጃ ጠቋሚው ደርድር እና currentSum (እንደ 0 ቀደም ብሎ የተጀመረው)።

እስቲ አንድ ምሳሌ እንመልከት-

ለምሳሌ

arr [] = {14, 1, -10, 20, 1} ፣ ድምር = 5

የተወሰኑ አሉታዊ ቁጥሮችን እና እንዲሁም የቁጥር ድምርን የያዘ የኢቲጀር ድርድር ሰጥተናል ፡፡ የተሰጠውን ቁጥር ፣ ድምርን የሚጨምር ንዑስ-ድርድርን መፈለግ አለብን ፡፡ መላውን ድርድር እያለፍን የአሁኑን ስማችንን ልንጠብቅ ይገባል ፣ ይህ ሊሆን የሚችል ንዑስ ድርድር ይሰጠናል ፡፡

i = 0, currentSum = 0

currentSum = currentSum + arr [i] => currentSum = 14 ፣ አሁን በእኛ የአሁኑ ሱም ውስጥ 14 አለን ፣ ከተጠቀሰው ድምር 5 ጋር እኩል መሆኑን እናጣራለን ፣ ያ ደግሞ ሐሰት ነው ፣ ከዚያ ካርታው የ currentSum-sum ማለት 14-5 = 9 ማለት ደግሞ ሐሰት ነው ፡፡ ስለዚህ የሚቀጥለውን ንጥረ ነገር እናልፋለን ፡፡ ስለዚህ የአሁኑን ስሙን እና እኔ ወደ ካርታው ውስጥ እንጨምራለን ፡፡

i = 1, currentSum = 14

currentSum = currentSum + arr [i] => 14 + 1 = 15, currentSum = 15, አሁን በእኛ የአሁኑ ሱም ውስጥ 15 አለን, ከተጠቀሰው ድምር ጋር እኩል መሆኑን እናረጋግጣለን ግን አላረካም, እኛ እንሄዳለን ካርታው የአሁኑን የሱም-ድምር ይ 15ል ፣ ይህም 5-10-XNUMX ነው ፣ ደግሞም ሐሰት ነው። ስለዚህ የአሁኑን ስሙን እና እኔ ወደ ካርታው ውስጥ እንጨምራለን ፡፡

i = 2 ፣ የአሁኑ ሱም = 15 ፣

currentSum = currentSum + arr [i] => 15 + (-10) ፣ currentSum = 5 ፣ አሁን በእኛ የአሁኑ ሱም ውስጥ 15 አለን ፣ ከተጠቀሰው ድምር 5 ጋር እኩል መሆኑን እናጣራለን እና ሁኔታው ​​እንዳገኘነው ረክቷል ፣ ውጤታችንን አገኘን ማለት ነው ፣ ከዚያ የንዑስ ክፍል 0 ን ማውጫ ማውጫዎችን እናተምበታለን።

ኮድ

ከተሰጠ ድምር ጋር ንዑስ ድርድርን ለማግኘት የ C + + ኮድ (መያዣዎች አሉታዊ ቁጥሮች)

#include<iostream>
#include<unordered_map>

using namespace std;

void getSubArray(int arr[], int n, int sum)
{
    unordered_map<int, int> map;
    int currentSum = 0;
    for (int i = 0; i < n; i++)
    {
        currentSum = currentSum + arr[i];
        if (currentSum == sum)
        {
            cout << "Sum found between index "<< 0 << " to index " << i << endl;
            return;
        }
        if (map.find(currentSum - sum) != map.end())
        {
            cout << "Sum found between index "<< map[currentSum - sum] + 1 << " to index " << i << endl;
            return;
        }
        map[currentSum] = i;
    }
    cout << " No such sub-array exists ";
}
int main()
{
    int arr[] = {14, 1, -10, 20, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    int sum = 5;
    getSubArray(arr, n, sum);
    return 0;
}
Sum found between index 0 to index 2

ከተሰጠ ድምር ጋር ንዑስ ድርድርን ለማግኘት የጃቫ ኮድ (መያዣዎች አሉታዊ ቁጥሮች)

import java.util.HashMap;

class printSubArraywithGivenSum
{
    public static void getSubArray(int[] arr, int n, int sum)
    {
        int currentSum = 0;
        HashMap<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < n; i++)
        {
            currentSum = currentSum + arr[i];
            if (currentSum - sum == 0)
            {
                System.out.println("Sum found between index "+ 0 + " to index " + i);
                return;
            }
            if (map.containsKey(currentSum - sum))
            {
                int val=map.get(currentSum-sum)+1;
                System.out.println("Sum found between index "+ val+" to index " + i);
                return;
            }
            map.put(currentSum, i);
        }
        System.out.println("No such sub-array exists");
    }
    public static void main(String[] args)
    {
        int[] arr = {14, 1, -10, -20, 2};
        int n = arr.length;
        int sum = 5;
        getSubArray(arr, n, sum);
    }
}
Sum found between index 0 to index 2

ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (ኤን) የት "N" በድርድሩ ውስጥ ያሉት ንጥረ ነገሮች ብዛት ነው።

የቦታ ውስብስብነት

ኦ (ኤን) የት "N" በድርድሩ ውስጥ ያሉት ንጥረ ነገሮች ብዛት ነው።