一种找到大于 X returns 错误数字的最小子数组的方法

Question

例如{1, 4, 45, 6, 0, 19}和数51应该return3，因为最小子数组中的元素个数加起来大于51 是 3: {4,45,6}`.

{7, 2, 5, 10, 1}和数字9应该return1，因为最小子数组中的元素数可能大于9是 {10}.

如果数组为 null 或空，或者数组没有大于给定数的子数组，则该方法必须 return -1。我不允许使用 java.util 中的数组包。我的目标是在 O(n) 时间内执行该方法。到目前为止，这是我的代码，如果数组没有大于给定数字的子数组，则 return 是一个 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 && left - right < smallest) {
            smallest = left - right;
            left++;
        } else
            sum -= arr[left];
        left++;
        if (sum > x && left - right < smallest)
            smallest = left - right;
    }

    return smallest;
}

编辑：也许我应该解释一下我试图用我的代码做什么，基本上我希望总和包含代码中的前两个元素，然后与每个 'if' 迭代进行比较，如果总和当前元素大于或小于 X，如果不是，我会提高正确的元素，如果是，我会删除第一个元素，即 'left' 一个。

数组{1, 4, 45, 6, 0, 19}和数字51 returns 2，虽然结果应该是3，不知道为什么，因为我的右边到达索引 3，即 6，左边到达索引 1，即 4，所以结果确实应该是 {4,45,6} 但它没有到达它。

Answer 1

这是我能做到的最好的了。

这是我的测试结果。

[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;
    }

}

一种找到大于 X returns 错误数字的最小子数组的方法

A method which finds the smallest subarray that's greater than X returns wrong number

java

arrays

sub-array