一道算法题,怎么样时间复杂度最低

当前有连续个x天
其中任意连续y天刮风次数之和不得大于z

这不是学生考试题,这是我们公司的一个业务情况。写出来不难,但是怎么样会更快呢?

判断是否满足条件吗?先求出最前面y天的和,然后删掉最前面一天的再补上尾巴后面那一天的这样依次判断。这样时间复杂度是O(x)

你的表述不清晰,看上去好像在对老天爷提需求。

正确表述:

判断在长度为 N 的数组中,是否存在至少连续 M 个元素满足指定条件。

参数:

  • 指定数组 arr
  • 最少满足条件的连续元素 minLength
  • 判断条件 predicate

转换成 Java 定义就是:

public static void main(String[] args) {
    int[] arr = {0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0};
    Predicate<Integer> predicate = i -> i > 0;
    int minLength = 3;

    // 求数组中是否存在至少连续3个大于0的数
    System.out.println(containsSubArray(arr, predicate, minLength));
}

private static boolean containsSubArray(
        int[] arr, Predicate<Integer> predicate, int minLength
) {
    return false;// TODO 这个是要实现的内容
}

那么这个 containsSubArray() 的具体实现内容如下:

    private static boolean containsSubArray(
            int[] arr, Predicate<Integer> predicate, int minLength
    ) {
        int counter = 0;  // 计数器
        for (int num : arr) {
            if (predicate.test(num)) {
                counter++;    // 遇到满足条件的数字,计数器累加
                if (counter >= minLength) {
                    return true;
                }
            } else {
                counter = 0;  // 遇到不满足的数字,计数器清零
            }
        }
        return false;
    }

XYZ 的数据范围最好提示一下