tối thiểu subarray đó là lớn hơn một chính

Question

Tôi có một mảng các số nguyên (không nhất thiết phải sắp xếp), và tôi muốn tìm một mảng con giáp mà tổng các giá trị của nó là tối thiểu, nhưng lớn hơn một giá trị cụ thể K

ví dụ :

đầu vào: mảng: {1,2,4,9,5}, giá trị chính: 10

đầu ra: {4,9}

Tôi biết đó là dễ dàng để làm điều này trong O(n^2) nhưng tôi muốn làm điều này trong O(n)

Ý tưởng của tôi: Tôi không thể tìm thấy anyway để điều này trong O(n) nhưng tất cả tôi có thể nghĩ là O(n^2) phức tạp thời gian.

Answer 1

Giả sử rằng nó chỉ có thể có giá trị dương.

Sau đó, thật dễ dàng.

Giải pháp là một trong các tiêu chí con liên tiếp tối thiểu (ngắn nhất) có tổng là > K.

Lấy hai chỉ mục, một cho bắt đầu của subarray, và một cho kết thúc (một trong quá khứ kết thúc), bắt đầu với end = 0 và start = 0. Khởi sum = 0; và 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; 
} 

Kể từ khi cả hai chỉ số chỉ được tăng lên, các thuật toán là O(n).

Answer 2

Thực hiện Java cho số dương và âm (không hoàn toàn chắc chắn về số âm) số hoạt động trong thời gian O (n) với không gian O (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; 
}