दो-सूचक और स्लाइडिंग विंडो पैटर्न

पैटर्न 1: लगातार विंडो (जैसे विंडो = 4 या कुछ पूर्णांक मान)

उदाहरण के लिए (-ve और ve) पूर्णांकों की एक सरणी दी गई है, जो आकार k की सन्निहित विंडो के लिए अधिकतम योग ढूंढती है।

पैटर्न 2:(परिवर्तनीय विंडो आकार) उदाहरण के साथ सबसे बड़ा सबरे/सबस्ट्रिंग: योग

• दृष्टिकोण:
  • पाशविक बल: सभी संभावित उपसरणी उत्पन्न करें और अधिकतम लंबाई वाली उपसरणी चुनें योग के साथ
• बेटन/इष्टतम: समय जटिलता को O(n) तक कम करने के लिए दो पॉइंटर और स्लाइडिंग विंडो का उपयोग करें

पैटर्न 3: उपसरणी/सबस्ट्रिंग की संख्या जहां जैसे sum=k.
इसे हल करना बहुत मुश्किल है क्योंकि यह मुश्किल हो जाता है कि कब विस्तार करना है (दाएं) या कब सिकुड़ना है (बाएं)।

इस समस्या को पैटर्न 2
का उपयोग करके हल किया जा सकता है समस्याओं को हल करने के लिए जैसे कि सबस्ट्रिंग की संख्या ज्ञात करना जहां योग =k.

• इसे इस प्रकार तोड़ा जा सकता है

  • उपसरणी ढूंढें जहां sum
  • उपसरणी ढूंढें जहां योग

पैटर्न 4: सबसे छोटी/न्यूनतम विंडो ढूंढें

पैटर्न 2 के लिए अलग-अलग दृष्टिकोण:
उदाहरण: योग के साथ सबसे बड़ा उपसरणी

public class Sample{
    public static void main(String args[]){
        n = 10;
        int arr[] = new int[n];

        //Brute force approach for finding the longest subarray with sum  k) break; /// optimization if the sum is greater than the k, what is the point in going forward? 
            }
        }

दो पॉइंटर्स और स्लाइडिंग विंडो का उपयोग करके बेहतर दृष्टिकोण

        //O(n n) in the worst case r will move from 0 to n and in the worst case left will move from 0 0 n as well so 2n
        int left = 0;
        int right =0;
        int sum = 0;
        int maxLen = 0;
        while(right k){
                sum = sum-arr[left];
                left  ;
            }
            if(sum 



इष्टतम दृष्टिकोण: 

हम जानते हैं कि यदि हमें उपसरणी मिल जाती है तो हम उसकी लंबाई को maxLen में संग्रहित करते हैं, लेकिन arr[right] जोड़ते समय यदि योग k से अधिक हो जाता है तो वर्तमान में हम sum = sum-arr[left] करके और बाएँ करके बाएँ को सिकोड़ रहे हैं। 

हम जानते हैं कि वर्तमान अधिकतम लंबाई maxLen है, यदि हम बाएं सूचकांक को सिकोड़ते रहते हैं तो हमें स्थिति ( maxLen वाला एक अन्य उपसरणी ढूंढें, तभी maxLen को अपडेट किया जाएगा।

एक इष्टतम दृष्टिकोण केवल बाईं ओर को सिकोड़ना होगा जब तक कि उपसरणी की लंबाई मैक्सलेन से अधिक न हो, जब उपसरणी शर्त को संतुष्ट नहीं कर रही हो (


        int right =0;
        int sum = 0;
        int maxLen = 0;
        while(right k){// this will ensure that the left is incremented one by one (not till the sum