Блог

Например, {1, 4, 45, 6, 0, 19} и число 51 должно возвращаться 3 , потому что количество элементов в наименьшем подмассиве, которые вместе больше 51 , равно 3: {4,45,6}` .

{7, 2, 5, 10, 1} и число 9 должно вернуться 1 , потому что число элементов в наименьшем возможном подмассиве больше, чем 9 есть {10} .

Если массив равен нулю или пуст, или в массиве нет подмассива, который больше заданного числа, метод должен вернуть -1. Мне не разрешено использовать пакет array из java.util. Моя цель — выполнить метод за O (n) время. Пока что это мой код, если в массиве нет подмассива, превышающего заданное число, он возвращает ошибку OutofBounds . У кого-нибудь есть подсказка?

 public static int smallestSubSum(int arr[], int x) {
    int left = 0, right = 1, smallest = 0;
    int sum = arr[right];

    for (int i = 1; i < arr.length; i  ) {
        if (sum > x)
            smallest = left - right;
        else
            right  ;
        sum  = arr[right];
        if (sum > x amp;amp; left - right < smallest) {
            smallest = left - right;
            left  ;
        } else
            sum -= arr[left];
        left  ;
        if (sum > x amp;amp; left - right < smallest)
            smallest = left - right;
    }

    return smallest;
}
 

Редактировать: возможно, мне следует объяснить, что я пытался сделать со своим кодом, в основном я хотел, чтобы сумма содержала первые два элемента в коде, а затем сравнивала с каждой итерацией «if», если сумма текущих элементов больше или меньше X, если нет, я поднимаю правильный элементчтобы пойти дальше, если да, я удаляю первый элемент, «левый».

Массив {1, 4, 45, 6, 0, 19} и число 51 возвращает 2, хотя результат должен быть равен 3. Я не знаю почему, потому что мой правый достигает индекса 3, который равен 6, а левый достигает индекса 1, который равен 4, поэтому результат действительно должен быть {4,45,6}, но он не доходит до него.

Это лучшее, что я мог сделать.

Вот мои результаты тестирования.

 [1, 4, 45, 6, 0, 19] -> 51
3
[7, 2, 5, 10, 1] -> 9
1
[1, 4, 45, 6, 0, 19] -> 200
-1
 

Я просто циклически перебирал массив с for помощью цикла. Всякий раз, когда общее количество превышало сумму X, я вычитал значения, пока общее количество не упало ниже суммы X.

Вот полный исполняемый код, с которым я тестировал.

 import java.util.Arrays;

public class SmallestSubarray {

    public static void main(String[] args) {
        int[] arr1 = new int[] { 1, 4, 45, 6, 0, 19 };
        int x1 = 51;
        System.out.println(Arrays.toString(arr1)   " -> "   x1);
        System.out.println(smallestSubSum(arr1, x1));

        int[] arr2 = new int[] { 7, 2, 5, 10, 1 };
        int x2 = 9;
        System.out.println(Arrays.toString(arr2)   " -> "   x2);
        System.out.println(smallestSubSum(arr2, x2));

        int[] arr3 = new int[] { 1, 4, 45, 6, 0, 19 };
        int x3 = 200;
        System.out.println(Arrays.toString(arr3)   " -> "   x3);
        System.out.println(smallestSubSum(arr3, x3));
    }

    public static int smallestSubSum(int arr[], int x) {
        if (arr == null || arr.length < 1) {
            return -1;
        }
        
        int sum = 0;
        int minCount = Integer.MAX_VALUE;
        int index = 0;

        for (int i = 0; i < arr.length; i  ) {
            sum  = arr[i];
            while (sum > x) {
                minCount = Math.min(i - index   1, minCount);
                sum -= arr[index];
                index  ;
            }
        }
        
        return (minCount == Integer.MAX_VALUE) ? -1 : minCount;
    }

}