किसी दिए गए योग के साथ एक उपसरणी ढूंढना एक आम समस्या है जो अक्सर कोडिंग साक्षात्कार और प्रतिस्पर्धी प्रोग्रामिंग में दिखाई देती है। इस समस्या को विभिन्न तकनीकों का उपयोग करके हल किया जा सकता है, जिनमें से प्रत्येक का समय जटिलता और स्थान जटिलता के संबंध में अपना-अपना समझौता है। इस लेख में, हम जावा में किसी दिए गए योग के साथ एक उपसरणी खोजने की समस्या को हल करने के लिए कई तरीकों का पता लगाएंगे।

समस्या का विवरण

पूर्णांकों की एक सरणी और एक लक्ष्य योग को देखते हुए, सरणी में एक सतत उपसरणी ढूंढें जो दिए गए योग में जुड़ती है। समस्या को दो मुख्य प्रकारों में विभाजित किया जा सकता है:

1. सकारात्मक संख्याओं के साथ उपसरणी: सरणी में केवल सकारात्मक संख्याएं होती हैं।
2. मिश्रित संख्याओं के साथ उपसरणी: सरणी में सकारात्मक और नकारात्मक दोनों संख्याएं होती हैं।

आइए इन प्रकारों को हल करने के लिए विभिन्न तरीकों का पता लगाएं।

दृष्टिकोण 1: क्रूर बल का उपयोग करना

क्रूर बल दृष्टिकोण में सभी संभावित उपसरणी की जांच करना और यह देखने के लिए उनके योग की गणना करना शामिल है कि उनमें से कोई भी लक्ष्य योग के बराबर है या नहीं। यह दृष्टिकोण दोनों वेरिएंट के लिए काम करता है लेकिन इसकी द्विघात समय जटिलता के कारण बड़े सरणियों के लिए अक्षम है।

कार्यान्वयन

public class SubarraySumBruteForce {
  public static int[] findSubarrayWithGivenSum(int[] arr, int targetSum) {
    int n = arr.length;
    for (int start = 0; start 
आउटपुट
Subarray found from index 1 to 3

विश्लेषण

• समय जटिलता: O(n²) सरणी के माध्यम से पुनरावृत्त होने वाले दो नेस्टेड लूप के कारण।
• अंतरिक्ष जटिलता: O(1) क्योंकि इनपुट सरणी से परे कोई अतिरिक्त स्थान का उपयोग नहीं किया जाता है।

दृष्टिकोण 2: स्लाइडिंग विंडो का उपयोग करना

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

कार्यान्वयन

public class SubarraySumSlidingWindow {
  public static int[] findSubarrayWithGivenSum(int[] arr, int targetSum) {
    int start = 0;
    int currentSum = 0;

    for (int end = 0; end  targetSum && start 
आउटपुट
Subarray found from index 1 to 3

विश्लेषण

• समय जटिलता: O(n) क्योंकि प्रत्येक तत्व को अधिकतम दो बार संसाधित किया जाता है।
• अंतरिक्ष जटिलता: O(1) क्योंकि किसी अतिरिक्त स्थान की आवश्यकता नहीं है।