关于我编写的子数组查找算法的平均与最坏时间复杂度的疑问

最坏时间复杂度确实是O(n²) #

你的代码在特定输入场景下会触发最坏情况：比如数组全为正数，且所有子数组的和都小于目标值（例如arr = [1,1,1,1]，target=10）。此时外层循环的每个i对应的内层循环k都会从i遍历到数组末尾，总操作次数为n + (n-1) + ... + 1 = n(n+1)/2，属于O(n²)量级。

编程题对时间复杂度的要求默认以最坏情况为标准，题目要求O(n)时，你的代码不符合要求，扣分是合理的。

平均情况是否为O(n)？ #

这个观点仅在特定输入分布下成立：

• 如果数组中频繁出现等于target的元素，或者子数组和很快超过target，内层循环会频繁提前break，此时平均操作次数接近O(n)。
• 但如果输入中最坏情况的场景占比不低，平均复杂度会接近O(n²)。

不过算法题的评判不会以平均复杂度为核心依据，必须保证所有合法输入都能达到要求的效率。

代码中的致命bug #

你的循环条件存在数组越界问题：i <= arr.length和k <= arr.length会导致当i或k等于数组长度时，访问arr[k]触发下标越界异常，应修改为i < arr.length和k < arr.length。

O(n)复杂度的可行解法 #

滑动窗口法（适用于数组全为正数的场景） #

利用正数子数组和单调递增的特性，用左右指针维护窗口边界，时间复杂度严格O(n)：

public static void findSubarray(int[] arr, int target) {
    int left = 0;
    int currentSum = 0;
    boolean found = false;
    for (int right = 0; right < arr.length; right++) {
        currentSum += arr[right];
        // 和超过目标值时，收缩左边界
        while (currentSum > target && left <= right) {
            currentSum -= arr[left];
            left++;
        }
        // 找到符合条件的子数组
        if (currentSum == target || arr[right] == target) {
            found = true;
            break;
        }
    }
    // 后续可根据found状态输出结果
}

前缀和+哈希表（适用于包含负数的场景） #

通过记录前缀和的出现位置，快速判断是否存在和为target的子数组，时间复杂度O(n)：

import java.util.HashMap;

public static void findSubarray(int[] arr, int target) {
    HashMap<Integer, Integer> prefixMap = new HashMap<>();
    prefixMap.put(0, -1); // 处理前缀和等于target的情况
    int currentPrefix = 0;
    boolean found = false;
    for (int i = 0; i < arr.length; i++) {
        currentPrefix += arr[i];
        // 若存在前缀和等于currentPrefix - target，说明中间子数组和为target
        if (prefixMap.containsKey(currentPrefix - target) || arr[i] == target) {
            found = true;
            break;
        }
        prefixMap.put(currentPrefix, i);
    }
    // 后续可根据found状态输出结果
}

内容的提问来源于stack exchange，提问作者Atlanticus