گھٽ ۾ گھٽ سائز سبريڊ سم


تڪليف جي سطح وچولو
بار بار پڇڻ ۾ Amazon ڪريو Goldman سيچ گوگل Microsoft جي
ڪيريو بائنري ڳولا ٻه پوتر

ڏنو هڪ صف هاڪاري عدد ۽ عدد جو انگ ، عدد ڪنگهواڙ نن subن نن theن جي گهٽ ۾ گهٽ سائيز ڳوليو جن جو مجموعو ايس (ڏنل قيمت) کان وڌيڪ يا وڌيڪ برابر هجي.

مثال

انٽرويو
نمبر [] = {2 ، 3 ، 1 ، 2 ، 4 ، 3}
ص = 7
پيداوار:
2 {سبراه [4 ، 3] 7 کي گھڻي آھي ۽ گھٽ ۾ گھٽ ڊيگهه}

گھٽ ۾ گھٽ سائز سبريڊ سم

نهايت ويجهڙائي گهٽ قيمت وارو سباري وارو سم

مٿين مسئلي کي حل ڪرڻ جي لاءِ نرالو انداز ٻه گولي وارو لوپ هلائڻ آهي ، جتي ٻاهرين لوپ سبري جي شروعاتي انڊيڪس جي نمائندگي ڪري ٿو ۽ اندروني لوپ کي سبيل جي ختم ٿيڻ واري انڊيڪس کي رقم سان مليل يا وڌيڪ ڏنل رقم جي برابر آهي.
جواب جي طور تي گهٽ ۾ گهٽ ڊگھائي سان ماتحت چونڊيو.

  1. اين ايس کي لامحدود طور تي شروع ڪريو.
  2. I = 0 کان n (شامل نه آهي) لاءِ لوپ هليو ، جتي ن صف ۾ عنصرن جو تعداد آهي ، ۽ قدم 3 ۽ 4 کي ورجائي.
  3. شروعاتي طور تي متغير رقم کي شروعاتي طور 0 ڪريو. ھڪڙي بولين متغير کي شروعاتي طور غلط ڪريو. j = (i + 1) کي n (شامل نه آھي) لاءِ nested لوپ کي ھليو ۽ شامل نه ڪيو وڃي ۽ ھر تجربي جي چڪاس تي ته آيا رقم گھڻي کان وڌيڪ آھي يا گهربل رقم جي برابر آھي ، جيڪڏھن اھو بھترين سيٽ آھي سچو مليو ۽ اين ايس کي گھٽ ۾ گھٽ اپڊيٽ ڪريو ANS ۽ (j - i) جئين (j - i) هن سبيل جي ڊيگهه آھي ۽ لوپ کي ٽوڙڻ. ايلس موجوده عنصر جي قيمت کي رقم ۾ شامل ڪيو.
  4. جيڪڏهن مليو غلط آهي ، جاچ ڪريو ته کُل رقم وڌيڪ آهي يا گهربل رقم جي برابر آهي جيڪڏهن اها اين ايس کي گهٽ ۾ گهٽ اپ ڊيٽ ڪيو وڃي ۽ (n - i) جيئن (n - i) سب ويري جي طويل آهي I ۽ شروع کان. آخري عنصر تي.
  5. جيڪڏهن اين ايس جي قيمت لامحدود آهي ، گهربل رقم سان گڏ هڪ ننayڙي زمين نه ملي ، واپسي 0 ، ٻي صورت واپس ۽.

جاوا ڪوڊ

public class MinimumSizeSubarray {
    private static int findMinimumSizeSubarray(int[] nums, int s) {
        int n = nums.length;
        int ans = Integer.MAX_VALUE;
        // Outer loop denotes starting index
        for (int i = 0; i < n; i++) {
            int sum = nums[i];
            boolean found = false;
            // Inner loop finds the ending index
            for (int j = i + 1; j < n; j++) {
                if (sum >= s) {
                    // Subarray found
                    int length = j - i;
                    ans = Math.min(ans, length);
                    found = true;
                    break;
                }

                // Add the current value to sum
                sum += nums[j];
            }

            if (!found) {
                // This handles the case of subarray from i to last
                if (sum >= s) {
                    int length = n - i;
                    ans = Math.min(ans, length);
                }
            }
        }
        
        // Subarray with required sum is not found
        if (ans == Integer.MAX_VALUE) {
            ans = 0;
        }
        
        return ans;
    }

    public static void main(String[] args) {
        int nums[] = new int[] {2, 3, 1, 2, 4, 3};
        int sum = 7;
        
        int minSize = findMinimumSizeSubarray(nums, sum);
        System.out.println(minSize);
    }
}

سي ++ ڪوڊ

#include <bits/stdc++.h>
using namespace std;

int findMinimumSizeSubarray(int *nums, int s, int n) {
    int ans = INT_MAX;
    // Outer loop denotes starting index
    for (int i = 0; i < n; i++) {
        int sum = nums[i];
        bool found = false;
        // Inner loop finds the ending index
        for (int j = i + 1; j < n; j++) {
            if (sum >= s) {
                // Subarray found
                int length = j - i;
                ans = std::min(ans, length);
                found = true;
                break;
            }
            // Add the current value to sum
            sum += nums[j];
        }
        
        if (!found) {
            // This handles the case of subarray from i to last
            if (sum >= s) {
                int length = n - i;
                ans = std::min(ans, length);
            }
        }
    }
    
    // Subarray with required sum is not found
    if (ans == INT_MAX) {
        ans = 0;
    }
        
    return ans;
}

int main() {
    int nums[] = {2, 3, 1, 2, 4, 3};
    int sum = 7;

    int minSize = findMinimumSizeSubarray(nums, sum, 6);
    cout<<minSize<<endl;
    
    return 0;
}
2

گھٽ ۾ گهٽ وڌايل سبريائون سم لاءِ پيچيدگي تجزيو

وقت جي پيچيدگي = اي (اين2
خلائي پيچيدگي = اي (1) 
جتي صف ۾ عناصر جو تعداد آهي.

گهٽ کان گهٽ سائز لاءِ تمام سٺو رستو سبري وارو سم

مسئلي کي حل ڪرڻ جو بهتر طريقو ٻه پوائنٽرز استعمال ڪرڻ آهي ، ptr1 ۽ ptr2 ، جتي ptr1 ماتحت جي شروعاتي انڊيڪس جي نمائندگي ڪري ٿو ۽ ptr2 ختم ٿيڻ واري انڊيڪس جي نمائندگي ڪري ٿو.

الورورٿم

  1. ptr1 ۽ ptr2 کي 0 (صفر) ۽ ويچاري رقم 0 (صفر) کي شروع ڪريو
  2. جڏهن ته رقم جي قيمت گهربل رقم کان گهٽ آهي ، پيٽر 2 تي موجود ويليو کي شامل ڪرڻ لاءِ ۽ اڳتي وڌايو ptr2.
  3. جڏهن ته رقم جي قيمت گهربل رقم کان وڌيڪ يا برابر آهي ، گهٽ ۾ گهٽ سب ويري کي تازه ڪاري ڪريو ، ۽ رقم کي ptr1 تي موجود رقم ختم ڪريو ۽ ptr1 اڳتي وڌو.
  4. ٻيهر 2 ۽ قدم 3 جي ٻيهر ورجائي وٺو جڏهن پيٽر 1 ڏنل قطار جي ڊيگهه کان گهٽ آهي.
  5. جيڪڏهن گهربل رقم سان ڪو به Subarray نه آهي ، واپسي 0 ، ٻي صورت ۾ گهٽ ۾ گهٽ لمبائي Subarray جي واپسي.

جاوا ڪوڊ

public class MinimumSizeSubarray {
    private static int findMinimumSizeSubarray(int[] nums, int s) {
        int n = nums.length;
        // Initialize ptr1, ptr2 and sum as 0
        int ptr1 = 0, ptr2 = 0, sum = 0;
        int ans = Integer.MAX_VALUE;

        // While ptr2 is less than n
        while (ptr2 < n) {
            // While the sum is less than s, add value present at ptr2 to sum and move ptr2 ahead
            while (sum < s && ptr2 < n) {
                sum += nums[ptr2++];
            }

            // While sum greater than or equals to s, update the minimum subarray length and remove value
            // present at ptr1 from sum and move ptr1 ahead
            while (sum >= s && ptr1 < n) {
                ans = Math.min(ans, ptr2 - ptr1);
                sum -= nums[ptr1++];
            }
        }

        // Subarray with required sum is not found
        if (ans == Integer.MAX_VALUE) {
            ans = 0;
        }

        return ans;
    }

    public static void main(String[] args) {
        int nums[] = new int[] {2, 3, 1, 2, 4, 3};
        int sum = 7;

        int minSize = findMinimumSizeSubarray(nums, sum);
        System.out.println(minSize);
    }
}

سي ++ ڪوڊ

#include <bits/stdc++.h> 
using namespace std; 
int findMinimumSizeSubarray(int *nums, int s, int n) { 
  // Initialize ptr1, ptr2 and sum as 0 
  int ptr1 = 0, ptr2 = 0, sum = 0; 
  int ans = INT_MAX; 
  // While ptr2 is less than n 
  while (ptr2 < n) { 
    // While the sum is less than s, add value present at ptr2 to sum and move ptr2 ahead 
    while (sum < s && ptr2 < n) { 
      sum += nums[ptr2++]; 
    } 
    // While sum greater than or equals to s, update the minimum subarray length and remove value 
    // present at ptr1 from sum and move ptr1 ahead 
    while (sum >= s && ptr1 < n) { 
      ans = std::min(ans, ptr2 - ptr1); 
      sum -= nums[ptr1++]; 
    } 
  } 
  // Subarray with required sum is not found 
  if (ans == INT_MAX) { 
    ans = 0; 
  } 
  return ans; 
} 
int main() { 
  int nums[] = {2, 3, 1, 2, 4, 3}; 
  int sum = 7; 
  int minSize = findMinimumSizeSubarray(nums, sum, 6); 
  cout<<minSize<<endl; 
  return 0; 
}
2

گھٽ ۾ گهٽ وڌايل سبريائون سم لاءِ پيچيدگي تجزيو

وقت جي پيچيدگي = اي (ن) 
خلائي پيچيدگي = اي (1)
جتي صف ۾ عناصر جو تعداد آهي.

حوالا