LC总结-子数组相关解题思路

1. 例题

2. 思路

三者都用到了动态规划的思想，但需要结合不同的数据结构进行处理。

2.1 LC560 和为 K 的子数组个数

做法：前缀和 + 哈希表

我们需要统计数组中和为 k 的子数组个数，可以先求前缀和数组 prefix（包含自身），然后推导一下递推式。

要找 [j, … ,i] 的和为k，其实就是找 prefix[i] - prefix[j - 1] = k

就是要找有多少个 prefix[j - 1] = prefix[i] - k

因此用一个哈希表来记录所有 prefix 的个数即可，对应代码如下：

class Solution {
    public int subarraySum(int[] nums, int k) {
        // 要找[j,...,i] == k，即 prefix[i] - prefix[j - 1] == k
        // 即要找有多少个 prefix[j - 1] == prefix[i] - k
        int n = nums.length;
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        int res = 0;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            // 代码中可以优化一下，不用 prefix 数组，而是用 sum 记录当前前缀和即可
            sum += nums[i];
            if (map.containsKey(sum - k)) {
                res += map.get(sum - k);
            }
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return res;
    }
}

2.2 LC862 和至少为 k 的最短子数组长度

在 LC560 上进行改编，变成了：和至少为 k、求最短子数组长度

不变的是要求前缀和，但要求最短子数组，可以使用一个单调的双端队列进行记录

当前前缀和和 - 队列第一个元素（下标）对应的前缀和 >= k 时，就更新一下长度，然后将这个元素出队。这个过程要保证队列中下标对应的前缀和是从小到大的。

Tips：求数组中 第一个符合xxx条件 的元素的位置，就要联想到单调栈、单调队列

class Solution {
    public int shortestSubarray(int[] nums, int k) {
        int n = nums.length;

        // 不包含当前元素的前缀和
        long[] preSum = new long[n + 1];
        for (int i = 0; i < n; i++) {
            preSum[i + 1] = preSum[i] + nums[i];
        }

        // 单调双端队列，存储下标
        Deque<Integer> dq = new ArrayDeque<Integer>();
        int minLength = Integer.MAX_VALUE;
        for (int i = 0; i <= n; i++) {
            long curSum = preSum[i];
            // 判断子数组和是否大于等于k
            while (!dq.isEmpty() && curSum - preSum[dq.peekFirst()] >= k) {
                minLength = Math.min(minLength, i - dq.pollFirst());
            }
            // 维护队列单调性，删除队尾大于等于 curSum 的前缀和下标
            while (!dq.isEmpty() && curSum <= preSum[dq.peekLast()]) {
                dq.pollLast(); // Tips：removeLast为空会异常，pollLast为空返回null
            }
            // 将当前下标加入队列
            dq.offerLast(i); // Tips：addLast超容量会异常，offerLast超容量返回false
        }
        minLength = minLength == Integer.MAX_VALUE ? -1 : minLength;
        return minLength;
    }
}

2.3 LC3097 或值至少为 k 的最短子数组长度

LC560 和 LC862 都可以用前缀和 + 数据结构解决问题，该题没办法再用前缀xxx，因为前缀和相减可以得到某一段子数组的区间和，但或运算不行，也没有 “前缀或” 这种概念。

因此需要另外一种记录方式，用一个数组记录每个位置到当前位置的 OR 值，并标记可以取的左端点的最大值。

如果 OR 值重复，则需要去重，留下左端点较大的那个。

class Solution {
    public int minimumSubarrayLength(int[] nums, int k) {
        int minLength = Integer.MAX_VALUE;

        // ors子数组，存储：从i开始的OR值，可取的左端点最大值（默认为i）
        List<int[]> ors = new ArrayList<>();

        for (int i = 0; i < nums.length; i++) {
            ors.add(new int[] { 0, i });
            int j = 0;
            for (int[] or : ors) {
                // 对所有 ors 子数组进行或运算
                or[0] |= nums[i];
                if (or[0] >= k) {
                    minLength = Math.min(minLength, i - or[1] + 1);
                }
                // 原地去重，参考LC27
                if (ors.get(j)[0] == or[0]) {
                  	// 取最大端点值，或运算一定会导致元素越非严格递增，所以可以原地去重（重点要理解）
                    ors.get(j)[1] = or[1];
                } else {
                    ors.set(++j, or);
                }
            }
            // 移除后面多余元素
            ors.subList(j + 1, ors.size()).clear();
        }
        return minLength == Integer.MAX_VALUE ? -1 : minLength;
    }
}