அதிகபட்ச அளவு துணை வரிசை தொகை k க்கு சமம்


சிரமம் நிலை நடுத்தர
அடிக்கடி கேட்கப்படுகிறது பேஸ்புக் மைக்ரோசாப்ட்
அணி ஹாஷ் ஹேஷிங்

In அதிகபட்ச அளவு துணை வரிசை தொகை k க்கு சமம் நாங்கள் ஒரு கொடுத்துள்ளோம் வரிசை முழு எண் மற்றும் ஒரு மதிப்பு k. K க்கு சமமான மிக நீளமான subarray இன் நீளத்தை நீங்கள் கண்டுபிடிக்க வேண்டும். அத்தகைய சப்ரே எதுவும் இல்லை என்றால் 0 ஐத் திருப்புக.

ஒரு அணுகுமுறை ஹேஸ்டேபிளைப் பயன்படுத்துவதோடு, தொகை k க்கு சமமாக இருக்கிறதா என்று சரிபார்த்து, அந்த சப்ரேயின் நீளத்தை k க்கு சமமாகக் கொடுக்க வேண்டும்.

உதாரணமாக:

உள்ளீடு:

அ [] = {10, 5, 2, 7, 1, 9};

k = 15;

வெளியீடு:

4

விளக்கம்:

Sub 15, 10}, {5, 5, 1}, {9, 5, 2, 7 like போன்ற 1 ஆக இருக்கக்கூடிய பல துணை வரிசைகள் உள்ளன, ஆனால் 15 உடன் மிக நீளமான துணை வரிசை {5, 2, 7, 1} அதன் நீளம் 4 ஆகும்.

அதிகபட்ச அளவு துணை வரிசை தொகை k க்கு சமம்

அல்காரிதம்

  1. டெக் இரண்டு மாறிகள் கூட்டுத்தொகை மற்றும் நீளத்தை வைத்து அவற்றை பூஜ்ஜியமாக அமைக்கவும், அதாவது கூட்டுத்தொகை = 0, நீளம் = 0.
  2. விசை மதிப்பு ஜோடியை அறிவிக்கவும் (வரைபடம் அல்லது ஹாஷ்-அட்டவணை)
  3. குறியீட்டு = 0 முதல் குறியீட்டு -1 வரை வளையத்தின் வழியாகச் சென்று பின்வரும் வழிகளில் தொடரவும்-
  4. வரிசை மற்றும் கூட்டுத்தொகையை சுருக்கமாக தொகுக்கவும்.
  5. கூட்டுத்தொகை k உடன் சமமாகக் கண்டறியப்பட்டால், நீளங்களின் மதிப்பை 1 ஆல் அதிகரிக்கச் செய்யுங்கள்.
  6. கூட்டுத்தொகையின் காசோலையுடன் மேலும் தொடரவும், இல்லையென்றால் அதை முக்கிய மதிப்பு ஜோடியாக சேர்க்கவும்.
  7. (கூட்டுத்தொகை - கே) ஹேஸ்டேபிளில் இருப்பதைக் கண்டால், குறியீட்டைப் பெறுங்கள்.
  8. மேலே வரி திருப்தி அடைந்தால், நீளங்களின் மதிப்பைப் புதுப்பிக்கவும்

அதிகபட்ச அளவு துணை வரிசை தொகை k க்கு சமம்

இந்த குறியீட்டை திறமையான நேர சிக்கலுடன் செயல்படுத்தக்கூடிய ஒரு சிறந்த வழியாக இது இருக்கும். எனவே எங்கள் முக்கிய யோசனை ஒரு ஹாஷ்மேப் மற்றும் சில மாறிகள் அதில் வெவ்வேறு மதிப்புகளை சேமிக்கப் போகிறது.

இந்த குறியீடு லூப்பைப் பயன்படுத்துகிறது, இது வரிசையின் நீளம் அடையும் வரை செல்லும். முதலில், இது arr [i] இன் மதிப்பைச் சுருக்கி, அதைச் சுருக்கமாகச் சேர்த்து, கூட்டுத்தொகையைப் புதுப்பிக்கப் போகிறது. கூட்டுத்தொகையின் மதிப்பு k இன் மதிப்புடன் சமமாக இருப்பதைக் கண்டால், அது புதுப்பித்து நீளங்களின் மதிப்பை 1 அதிகரிக்கும்.

ஸ்டோர்வால் (இது ஒரு ஹாஷ்மேப் மாறி) ஒரு வரைபடத்தில் கூட்டுத்தொகையின் மதிப்பைக் கொண்டிருக்கிறதா என்பதையும், ஒரு வரைபடத்தில் ஒரு சுருக்கமாக சுருக்கத்தைக் கொண்டிருக்கவில்லை என்றால் அது வரைபடத்தில் ஒரு நுழைவை வைத்து, வரைபடத்தில் கூட்டுத்தொகை மற்றும் குறியீட்டின் மதிப்பு.

அடுத்ததாக ஸ்டோர்வால் விசையை (கூட்டுத்தொகை - கே) வடிவத்தில் உள்ளதா என சரிபார்க்கப் போகிறது, அப்படியானால் அது நீளங்களை (குறியீட்டு - ஸ்டோர்வால் (கூட்டுத்தொகை - கே) உடன் ஒப்பிட்டு, நீளம் குறைவாக இருந்தால் ( குறியீட்டு - ஸ்டோர்வால் (கூட்டுத்தொகை - கே)) பின்னர் அது நீளங்களை = (குறியீட்டு - ஸ்டோர்வால் (கூட்டுத்தொகை - கே)) ஆக்கும், மேலும் இது எங்கள் அதிகபட்ச நீளமான சப்அரேயை k க்கு சமமான ஒரு கூட்டுத்தொகையும், கடைசி வருவாய் நீளமும் கண்டுபிடிக்கும் வரை தொடர்கிறது. .

கொடுக்கப்பட்ட வரிசை:

arr = {10, 5, 2, 7, 1, 9}

i = 0; sumation = 10, // sumation + = arr [i]

sumation == k // (k க்கு சமமான சுருக்கத்தை சரிபார்க்கவும்) // இங்கே இல்லை

if (! storeVal.containsKey (தொகை))

storeVal.put (தொகை, i) / * ஒவ்வொரு முறையும் இது கூட்டுத்தொகை மற்றும் குறியீட்டின் மதிப்புகளை வரைபடத்தில் முக்கிய மதிப்பு ஜோடியாக வைக்கும் * /

if (storeVal.containsKey (sumation - k)) // இங்கே இல்லை

அது தொடரும், அது நிபந்தனையை பூர்த்தி செய்யும் வரை தடுப்புக்குள் நுழையாது, அது குறியீட்டு = 4 இல் திருப்தி அளிக்கும், மேலும் சில செயல்பாடுகள் செயல்படுகின்றன, மேலும் சரியான பதிலைப் பெறுவோம்.

அதிகபட்ச அளவு சப்அரே தொகைக்கு சி ++ இல் செயல்படுத்தல் k க்கு சமம்

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int lenOfSubArray(int arr[], int n, int k)
{
  int summation = 0, lengths = 0;
  map<int, int> storeVal;
  for (int index = 0; index < n; index++)
  {
    //sums up the array
    summation += arr[index];
    //check if summation is equals to k
    if (summation == k)
    {
      lengths = index + 1;
    }

    if (storeVal.find(summation) == storeVal.end())
    {
      //store the values as a key value pair in
      //map
      storeVal[summation] = index;
    }

    if (storeVal.find(summation - k) != storeVal.end())
    {
      //updation of lengths
      if (lengths < (index - storeVal[summation - k]))
      {
        lengths = index - storeVal[summation - k];
      }
    }
  }

  return lengths;
}

int main()
{
  int arr[] = { 2, 5, 7, 3, 7, 9, 1 };
  int k = 17;
  int n = sizeof(arr) / sizeof(arr[0]);
  cout << "Length of Longest Substring is:" << lenOfSubArray(arr, n, k);
  return 0;
}
Length of Longest Substring is: 4

ஜாவாவில் அதிகபட்ச அளவு சப்அரே தொகைக்கு செயல்படுத்தல் k க்கு சமம்

import java.util.*;
import java.io.*;
class findMaxSubArray {
    public static int lenOfSubArray(int arr[], int n, int k) {
        int summation = 0, lengths = 0;
        HashMap<Integer, Integer> storeVal = new HashMap<>();
        for (int index = 0; index<n; index++) {
            //sums up the array
            summation += arr[index];
            //check if summation is equals to k
            if (summation == k) {
                lengths = index + 1;
            }
            if (!storeVal.containsKey(summation)) {
                //store the values as a key value pair in
                //map
                storeVal.put(summation, index);
            }
            if (storeVal.containsKey(summation - k)) {
                //updation of lengths
                if (lengths<(index - storeVal.get(summation - k))) {
                    lengths = index - storeVal.get(summation - k);
                }
            }
        }
        return lengths;
    }
    //Driver code
    public static void main(String args[]) {
        int arr[] = { 2, 5, 7, 3, 7, 9, 1 };
        int k = 17;
        int n = arr.length;
        System.out.println("Length of Longest Substring is:" + lenOfSubArray(arr, n, k));
    }
}
Length of Longest Substring is:4

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

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

 ஓ (n) n என்பது வரிசையின் அளவு.

துணை இடம்

 ஓ (n) n என்பது வரிசையின் அளவு.

குறிப்புகள்