几个数组相关常见算法题

题目一

给定一个正整数组成的无序数组arr，

给定一个正整数值k 找到arr的所有子数组里，

哪个子数组的累加和等于k，并且是长度最大的返回其长度

public static int getMaxLength(int[] arr, int k) {
    int sum = 0;
    int R = 0;
    int max = 0;
    for (int L = 0; L < arr.length; L++) {
        while (R < arr.length && sum + arr[R] <= k) {
            sum += arr[R++];
        }
        if (sum == k) {
            max = Math.max(max, R - L);
        }
        if (L < R) {
            sum -= arr[L];
        } else {
            R++;
        }
    }
    return max;
}

题目二

给定一个整数组成的无序数组arr，

给定一个整数值k 找到arr的所有子数组里，

哪个子数组的累加和等于k，并且是长度最大的返回其长度

可以看到，这题与上一题的区别就在于数组中元素和 k 不再只是正整数

public static int getMaxLength(int[] arr, int k) {
    HashMap map = new HashMap<>();
    map.put(0, -1);
    int preSum = 0;
    int max = 0;
    for (int i = 0; i < arr.length; i++) {
        preSum += arr[i];
        if (map.containsKey(preSum - k)) {
            max = Math.max(max, i - map.get(preSum - k));
        }
        if (!map.containsKey(preSum)) {
            map.put(preSum, i);
        }
    }
    return max;
}

题目三

给定一个整数组成的无序数组arr，值可能正、可能负、可能0

给定一个整数值K 找到arr的所有子数组里，

哪个子数组的累加和<=K，并且是长度最大的 返回其长度

这题和上一题的却别就在于子数组累加和不再是等于，而是 <= k

public static int getMaxLength(int[] arr, int k) {
    int N = arr.length;
    int[] minSum = new int[N];
    int[] minSumEnd = new int[N];
    minSum[N - 1] = arr[N - 1];
    minSumEnd[N - 1] = N - 1;
    for (int i = N - 2; i >= 0; i--) {
        if (minSum[i + 1] <= 0) {
            minSum[i] = arr[i] + minSum[i + 1];
            minSumEnd[i] = minSumEnd[i + 1];
        } else {
            minSum[i] = arr[i];
            minSumEnd[i] = i;
        }
    }
    int R = 0;
    int max = 0;
    int sum = 0;
    for (int L = 0; L < N; L++) {
        while (R < N && sum + minSum[R] <= k) {
            sum += minSum[R];
            R = minSumEnd[R] + 1;
        }
        max = Math.max(max, R - L);
        if (L < R) {
            sum -= arr[L];
        } else {
            R++;
        }
    }
    return max;
}