न्यूनतम subarray जो एक कुंजी

Question

मैं पूर्णांकों (जरूरी हल नहीं) की एक सरणी है की तुलना में बड़ा है, और मैं एक सन्निहित subarray अपने मूल्यों की जो राशि कम से कम कर रहे हैं खोजने के लिए चाहते हैं, लेकिन एक विशिष्ट मूल्य K

से भी बड़ा जैसे :

इनपुट: सरणी: {1,2,4,9,5}, कुंजी मूल्य: 10

उत्पादन: {4,9}

मैं जानता हूँ कि यह O(n^2) में यह करने के लिए आसान है, लेकिन मैं O(n)

मेरा विचार में ऐसा करना चाहते हैं: मुझे O(n) में वैसे भी नहीं मिला, लेकिन मुझे लगता है कि O(n^2) समय जटिलता थी।

Answer 1

मान लें कि इसमें केवल सकारात्मक मूल्य हो सकते हैं।

फिर यह आसान है।

समाधान न्यूनतम (सबसे कम) संगत subarrays में से एक है जिसका योग > K है।

दो इंडेक्स लें, एक सबएरे की शुरुआत के लिए, और अंत में एक (अंत में एक), end = 0 और start = 0 से शुरू करें। आरंभ sum = 0; और min = infinity

while(end < arrayLength) { 
    while(end < arrayLength && sum <= K) { 
     sum += array[end]; 
     ++end; 
    } 
    // Now you have a contiguous subarray with sum > K, or end is past the end of the array 
    while(sum - array[start] > K) { 
     sum -= array[start]; 
     ++start; 
    } 
    // Now, you have a _minimal_ contiguous subarray with sum > K (or end is past the end) 
    if (sum > K && sum < min) { 
     min = sum; 
     // store start and end if desired 
    } 
    // remove first element of the subarray, so that the next round begins with 
    // an array whose sum is <= K, for the end index to be increased 
    sum -= array[start]; 
    ++start; 
} 

दोनों सूचकांकों के बाद से ही बढ़ती है, एल्गोरिथ्म O(n) है।

Answer 2

ओ (1) अंतरिक्ष के साथ ओ (एन) समय में काम करता है जो सकारात्मक और नकारात्मक (नकारात्मक संख्याओं के बारे में पूरी तरह से सुनिश्चित नहीं) के लिए जावा कार्यान्वयन।

public static int findSubSequenceWithMinimumSumGreaterThanGivenValue(int[] array, int n) { 

    if (null == array) { 
     return -1; 
    } 

    int minSum = 0; 
    int currentSum = 0; 
    boolean isSumFound = false; 
    int startIndex = 0; 
    for (int i = 0; i < array.length; i++) { 
     if (!isSumFound) { 
      currentSum += array[i]; 
      if (currentSum >= n) { 
       while (currentSum - array[startIndex] >= n) { 
        currentSum -= array[startIndex]; 
        startIndex++; 
       } 
       isSumFound = true; 
       minSum = currentSum; 
      } 
     } else { 
      currentSum += array[i]; 
      int tempSum = currentSum; 
      if (tempSum >= n) { 
       while (tempSum - array[startIndex] >= n) { 
        tempSum -= array[startIndex]; 
        startIndex++; 
       } 
       if (tempSum < currentSum) { 
        if (minSum > tempSum) { 
         minSum = tempSum; 
        } 
        currentSum = tempSum; 
       } 
      } else { 
       continue; 
      } 
     } 
    } 
    System.out.println("startIndex:" + startIndex); 
    return minSum; 
}