ከ 0 ድምር ጋር ንዑስ ቡድን ካለ ይፈልጉ  


የችግር ደረጃ መካከለኛ
ውስጥ በተደጋጋሚ ተጠየቀ Citrix ዴ ሻው ጎልድማን ሳክስ በእርግጥም MakeMyTrip ኦዮ ክፍሎች Paytm TCS
ሰልፍ ሃሽ

ችግሩ “ከ 0 ድምር ጋር ንዑስ ቡድን ካለ ይፈልጉ” የሚለው እንደተሰጠ ይገልጻል ኢንቲጀር ደርድር እንዲሁም አሉታዊ ቁጥሮችን የያዘ። የችግሩ መግለጫ ማንኛውም ንዑስ ንዑስ ክፍል ቢያንስ ቢያንስ 1. ይህ ንዑስ ድርድር ከ 1 ጋር እኩል የሆነ ድምር ሊኖረው እንደሚገባ ይጠይቃል።

ለምሳሌ  

ከ 0 ድምር ጋር ንዑስ ቡድን ካለ ይፈልጉጭንቅላታም መያያዣ መርፌ

arr[] = {2,1,-3,4,5}
yes

ማስረጃ

እዚህ ከጠቋሚ 0 እስከ 2 ያሉት ንጥረ ነገሮች ድምር 0 አላቸው ፡፡

arr[] = {4,1,-4,5,1}
yes

ማስረጃ

ድምር 0 ያለው ንዑስ ድርድር የለም።

አልጎሪዝም  

  1. ያውጅ ሀ አዘጋጅ.
  2. ያስጀምሩ ድምር 0 ነው.
  3. ድርድርን ያቋርጡ ፣ ሳሉ እኔ <n (የድርድሩ ርዝመት)።
    1. ድምርን ወደ arr [i] ያክሉ እና ወደ ድምር ያከማቹ።
    2. ከሚከተሉት ሁኔታዎች ውስጥ አንዳቸውም እውነት መሆናቸውን ያረጋግጡ-
      1. ድምር == 0 / arr [i] == 0 / Set ከተዋቀረ የድምር ዋጋን ከያዘ።
      2. እውነት ከሆነ እንግዲያውስ እውነቱን ተመለስ።
    3. ድምርን ወደ ስብስቡ ያክሉ።
  4. ወደ ሐሰት መመለስ

ማስረጃ

ከ 0. ጋር እኩል በሆነ ድምር ማንኛውም ንዑስ ድርድር መኖር አለመኖሩን ለማወቅ የሚጠይቅ የችግር መግለጫ አግኝተናል ይህንን ለመፍታት ይህንን ችግር ለመፍታት Set ን እንጠቀማለን ፡፡ የተሰጠ ድርድርን ንጥረ ነገሮች ወደ ሴቲቱ ውስጥ እናከማቸዋለን ፡፡ ከዚያም በአንድ ጊዜ እሴቱን በድምሩ ውስጥ ይጨምሩ እና በስብስብ ውስጥ ካለው የአሁኑ ድምር ጋር ንዑስ-ድርድር ማዛመጃ ካለ ያረጋግጡ ወይም ድምር ራሱ እኩል ነው 0. ከድምሩ 0 ጋር ንዑስ-ድርድር ካለ ከተገኘ ከዚያ እንመለሳለን እውነት ነው

ተመልከት
ከ k የበለጠ ወይም እኩል የሆኑ ዋና ድግግሞሾች ያላቸው ቁጥሮች

ማንኛውም ንዑስ-ድርድር ድምር 0 ያለው ሆኖ ካልተገኘ ታዲያ እኛ ከጉበኙ ውጭ ሐሰትን እንመለሳለን ፡፡ ደግሞም ፣ አንድ ነገር አለ ፣ ማንኛውም ንጥረ ነገር 0 ከሆነ እኛ ደግሞ ወደ እውነት እንመለሳለን ምክንያቱም አንድ ንጥረ ነገር ራሱ የአንድ ነጠላ አባል ንዑስ ድርድር ነው። ስለዚህ አንድ እንደዚህ ያለ ንዑስ ድርድር አገኘን ማለት ነው ፡፡

እዚህ በኮዱ ውስጥ የቦሊያን ተግባር እናውጃለን ፣ እሱ እውነትም ይሁን ውሸት ይመለሳል ፣ ንዑስ ድርድር ከተገኘ ወደ እውነት ይመለሳል ፣ አለበለዚያ ሐሰተኛ ይሆናል ፡፡

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

ለምሳሌ

arr [] = {- 3,2,1,9,6}

እዚህ በኮዱ ውስጥ አንድ ድርድርን እያለፍን ድምር እና አመራን [i] እንጨምራለን እና ወደ ድምር እናከማቸዋለን እና ከዚያ ከተጣራ በኋላ ድምር == 0 ወይም arr [i] ከ 0 ጋር እኩል ከሆነ ወይም Set የደምር ዋጋን ይይዛል ፣ ከተጠቀሰው ሁኔታ አንዳችን የሚረካ ከሆነ ወደ እውነት እንመለሳለን እና ከዚያ ወደ ሴቱ ውስጥ ድምርን እንጨምራለን ፡፡

የትኛውም ንዑስ-ድርድር ካልተገኘ ታዲያ ወደ ሐሰት እንመለሳለን ፡፡

ድምር = 0 ፣ አዘጋጅ = {}

i = 0, arr [i] = -3

ድምር = ድምር + arr [i] => 0 + - 3 = -3

ድምር == 0 ወይም arr [i] ከ 0 ጋር እኩል ከሆነ ወይም Set የደምር ዋጋን ከያዘ ሦስቱ ሐሰተኞች ናቸው ፣ ስለሆነም እዚህ ምንም አናደርግም እና ወደ -3 ወደ ሴቱ እንጨምራለን።

i = 1, arr [i] = 2

ድምር = ድምር + arr [i] => -3 + 2 = -1

ድምር == 0 ወይም arr [i] ከ 0 ጋር እኩል ከሆነ ወይም Set የደምር ዋጋን ከያዘ ሦስቱ ሐሰተኞች ናቸው ፣ ስለሆነም እዚህ ምንም አናደርግም እና ወደ -1 ወደ ሴቱ እንጨምራለን።

i = 2, arr [i] = 1

ድምር = ድምር + arr [i] => -1 + 1 = 0

ድምር == 0 ሁኔታ እዚህ ከተሟላ ስለዚህ ወደ እውነት ተመለስን ማለት ድምር 0 ንዑስ ድርድር አገኘን ማለት ነው ፡፡

ተመልከት
II Leetcode Solution II ን ክምችት ለመግዛት እና ለመሸጥ የተሻለው ጊዜ

ውጤት-አዎ ድምር 0 ንዑስ ድርድር አለ ፡፡

ኮድ  

ከ 0 ድምር ጋር ንዑስ ቡድን ካለ ለመፈለግ የ C ++ ኮድ

#include<iostream>
#include<unordered_set>

using namespace std;

bool isSubArrayZero(int arr[], int n)
{
    unordered_set<int> Set;
    int sum = 0;
    for (int i = 0 ; i < n ; i++)
    {
        sum += arr[i];
        if (sum == 0 || Set.find(sum) != Set.end())
            return true;

        Set.insert(sum);
    }
    return false;
}
int main()
{
    int arr[] = {-3, 2, 1, 9, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
    if (isSubArrayZero(arr, n))
        cout << "Yes, a sub-array with sum 0 exist";
    else
        cout << "No, a sub-array with sum 0 does not exist";
    return 0;
}
Yes, a sub-array with sum 0 exist

ከ 0 ድምር ጋር ንዑስ ክፍል ካለ ለመፈለግ የጃቫ ኮድ

import java.util.Set;
import java.util.HashSet;

class sumOfSubArrayZero
{
    public static Boolean isSubArrayZero(int arr[])
    {
        Set<Integer> set = new HashSet<Integer>();
        int Sum = 0;
        for (int i = 0; i < arr.length; i++)
        {
            Sum += arr[i];
            if (arr[i] == 0 || Sum == 0 || set.contains(Sum))
                return true;

            set.add(Sum);
        }
        return false;
    }
    public static void main(String arg[])
    {
        int arr[] = {-3, 2, 1, 9, 6};
        if (isSubArrayZero(arr))
            System.out.println("Yes, a subarray with sum 0 exists");
        else
            System.out.println("No, a subarray with sum 0 does not exist");
    }
}
Yes, a subarray with sum 0 exists

ውስብስብነት ትንተና  

የጊዜ ውስብስብነት

ሆይ (n) የት “N” በድርድሩ ውስጥ ያሉት ንጥረ ነገሮች ብዛት ነው። ይህ ሁሉ የተቻለው ሀሽ ሴትን በመጠቀም ምክንያት በ (1) ጊዜ ውስጥ አስገባን ፣ ፍለጋን ፣ መሰረዝን እንድናከናውን ያስችለናል ፡፡

የቦታ ውስብስብነት

ሆይ (n) የት “N” በድርድሩ ውስጥ ያሉት ንጥረ ነገሮች ብዛት ነው። በተፈጠረው የሃሽ ስብስብ ውስጥ ቢበዛ n አካላት ሊኖሩ ስለሚችሉ ፣ የቦታ ውስብስብነት መስመራዊ ነው።