java—找到大于x的最小子数组的方法返回错误的数字

fnatzsnv 于 2021-07-03 发布在 Java

关注(0)|答案(1)|浏览(273)

例如， {1, 4, 45, 6, 0, 19} 号码呢 51 你应该回来 3 ，因为最小子数组中的元素数加起来大于 51 是 3: {4,45,6}.{7, 2, 5, 10, 1}号码呢9你应该回来1，因为最小子数组中的元素数可能大于9是{10}` .
如果数组为null或空，或者数组没有大于给定数字的子数组，则该方法必须返回-1。我不允许使用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 && left - right < smallest) {
            smallest = left - right;
            left++;
        } else
            sum -= arr[left];
        left++;
        if (sum > x && left - right < smallest)
            smallest = left - right;
    }

    return smallest;
}

编辑：也许我应该解释一下我试图用我的代码做什么，基本上我想让总和包含代码中的前两个元素，然后与每个“如果”迭代进行比较如果当前元素的总和大于或小于x，如果不是，我提高右边的元素更进一步，如果是，我删除第一个元素，左边的元素。
{1，4，45，6，0，19}和数字51的数组返回2，即使结果应该是3。我不知道为什么，因为我的右边达到了索引3，它是6，左边达到了索引1，它是4，所以结果应该是{4，45，6}，但它没有达到它。

Java Arrays sub-array

来源：https://stackoverflow.com/questions/65156867/a-method-which-finds-the-smallest-subarray-thats-greater-than-x-returns-wrong-n

1条答案

按热度按时间

hjqgdpho1#

这是我能做的最好的了。
这是我的测试结果。

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

}

赞(0）回复(0）举报 2021-07-03

我来回答

java—找到大于x的最小子数组的方法返回错误的数字

1条答案

相关问题

热门标签

最新问答