கொடுக்கப்பட்ட தொகையுடன் துணை வரிசையைக் கண்டறியவும் (எதிர்மறை எண்களைக் கையாளுகிறது)


சிரமம் நிலை நடுத்தர
அடிக்கடி கேட்கப்படுகிறது அமேசான் கூப்பன் டுனியா Delhivery GE ஹெல்த்கேர் தகவல் எட்ஜ் மூன்ஃப்ராக் ஆய்வகங்கள்
அணி ஹாஷ் நெகிழ் சாளரம்

“கொடுக்கப்பட்ட தொகையுடன் சப்ரேயைக் கண்டுபிடி (எதிர்மறை எண்களைக் கையாளுகிறது)” சிக்கல் உங்களுக்கு வழங்கப்பட்டுள்ளது என்று கூறுகிறது முழு வரிசை, எதிர்மறை முழு எண்களையும், “தொகை” எனப்படும் எண்ணையும் கொண்டுள்ளது. சிக்கல் அறிக்கை துணை வரிசையை அச்சிட கேட்கிறது, இது கொடுக்கப்பட்ட எண்ணை “தொகை” என்று அழைக்கிறது. எங்கள் வெளியீட்டில் ஒன்றுக்கு மேற்பட்ட துணை வரிசைகள் இருந்தால், அவற்றில் ஏதேனும் ஒன்றை அச்சிடுக.

உதாரணமாக

கொடுக்கப்பட்ட தொகையுடன் துணை வரிசையைக் கண்டறியவும் (எதிர்மறை எண்களைக் கையாளுகிறது)

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. வரிசையில் பயணிக்கவும், நான் <n,
    1. CurrentSum மற்றும் வரிசை உறுப்பு ஆகியவற்றின் மதிப்பைச் சுருக்கி, அதை currentSum இல் சேமிக்கவும்.
    2. CurrentSum தொகைக்கு சமமாக இருக்கிறதா என்று சோதிக்கவும்.
      • உண்மை என்றால், குறியீட்டை 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, இப்போது நம்முடைய currentSum இல் 14 உள்ளது, கொடுக்கப்பட்ட தொகைக்கு 5 க்கு சமமாக இருக்கிறதா என்று சோதிப்போம், அது தவறானது, பின்னர் வரைபடத்தில் உள்ளதா என்பதை சரிபார்க்கிறோம் currentSum-sum அதாவது 14-5 = 9 என்பதும் தவறானது. எனவே அடுத்த உறுப்பு வழியாக செல்வோம். எனவே நாம் தற்போதைய சம் மற்றும் ஐ வரைபடத்தில் சேர்க்கிறோம்.

i = 1, currentSum = 14

currentSum = currentSum + arr [i] => 14 + 1 = 15, currentSum = 15, இப்போது நம் நடப்பு சம்மில் 15 உள்ளது, அது கொடுக்கப்பட்ட தொகைக்கு சமமாக இருக்கிறதா என்று சோதிப்போம், ஆனால் அது திருப்தி அடையவில்லை, நாங்கள் சென்றால் வரைபடத்தில் நடப்பு சம்-தொகை உள்ளது, அது 15-5-10 என்பதும் தவறானது. எனவே நாம் தற்போதைய சம் மற்றும் ஐ வரைபடத்தில் சேர்க்கிறோம்.

i = 2, currentSum = 15,

currentSum = currentSum + arr [i] => 15 + (-10), currentSum = 5, இப்போது நம்முடைய currentSum இல் 15 உள்ளது, கொடுக்கப்பட்ட தொகைக்கு 5 சமமாக இருக்கிறதா என்று சோதிப்போம், மேலும் அந்த நிலை திருப்தி அடைந்தது, அதாவது எங்கள் வெளியீட்டைப் பெற்றுள்ளோம், பின்னர் சப்ரே 0 இன் குறியீடுகளை i க்கு அச்சிடுவோம்.

குறியீடு

கொடுக்கப்பட்ட தொகையுடன் துணை வரிசையைக் கண்டறிய சி ++ குறியீடு (எதிர்மறை எண்களைக் கையாளுகிறது)

#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

சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

ஓ (என்) எங்கே “என்” என்பது வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை.

விண்வெளி சிக்கலானது

ஓ (என்) எங்கே “என்” என்பது வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை.