秒杀子数组类题目

大家应该多多少少都见过几个「子数组」相关的题目，今天特意把常考的相关题目搜集了一波，进行分类整理总结，所以文章很硬核，记得收藏➕关注！

先给大家明确两个概念：「子数组」「子序列」，相信肯定有很多人傻傻分不清楚

「子数组」：必须连续，即子数组中的元素必须在原数组中连续。可以看道入门题 最大子数组和 加深理解

「子序列」：可不连续，即子序列中的元素在原数组中可非连续。可以看道入门题 最长递增子序列 加深理解，关于本题的详细讲解可见 动态规划设计：最长递增子序列

举个简单的例子，对于数组nums = [1,2,3,4]，其中[1,2]、[2,3]均为子数组，而[2,4]、[1,3,4]均为子序列

好了，正式进入本文的主要内容。如正上方列举的 9 道题目，可以简单的分为三类，使用的方法可分为三种，即：「前缀和」「滑动窗口」「动态规划」。下面具体题目具体分析

前缀和解决子数组问题

关于「前缀和」的详细介绍可见 前缀和数组

这一类「子数组问题」存在两个共同的特点：

• 处理子数组中元素之和 (研究对象)
• 给出了具体的限定 (约束条件)，如：和为k的倍数的子数组

和为 K 的子数组

详情可见题目 和为 K 的子数组

这个题目算是一个入门款的前缀和问题，借鉴两数和的思路，利用HashMap

​x
public int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> preSum = new HashMap<>();
    // 注意：需要单独加 (0, 1)
    preSum.put(0, 1);

    int sum = 0;
    int res = 0;
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];
        int target = sum - k;
        if (preSum.containsKey(target)) res += preSum.get(target);
        preSum.put(sum, preSum.getOrDefault(sum, 0) + 1);
    }
    return res;
}

这里值得注意的一点：在循环开始之前，往preSum中加了一行数据preSum.put(0, 1)。为什么需要这样操作呢？？

现在设想一种情况，nums = [1,2,3], k = 6，显然这个样例是存在满足条件的子数组，即：[1,2,3]

当i = 2, sum = 6时，此时target = sum - k = 0，如果不加preSum.put(0, 1)，结果就会出错！！！

和可被 K 整除的子数组

详情可见题目 和可被 K 整除的子数组

如果我们需要求区间为[i, j]子数组的和，即为preSum[j] - preSum[i - 1]，而题目的要求是元素之和可被k整除的子数组的个数，所以只需要找出所有(preSum[j] - preSum[i - 1]) % k == 0的区间即可。很容易想到可以像下面这样写：

xxxxxxxxxx
// 关键代码
for (int j = 1; i < preSum.length; j++) {
    for (int i = 0; i < j; i++) {
        if ((preSum(j) - preSum[i - 1]) % k == 0) res++;
    }
}

简单粗暴，可惜超时！！😭😭😭

这个题目的优化涉及到数学上的一个概念，下面先介绍一下这个理论

xxxxxxxxxx
(preSum[j] - preSum[i - 1]) % k == 0
preSum[j] % k - preSum[i - 1] % k == 0
preSum[j] % k == preSum[i - 1] % k

所以对于preSum[j]，我们只需要找是否存在preSum[i - 1]，使得preSum[j] % k == preSum[i - 1] % k

相应的代码如下：

xxxxxxxxxx
public int subarraysDivByK(int[] nums, int k) {
    int ans = 0;
    int sum = 0;
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, 1);
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];
        // 这样处理是为了把负数转换成相对应的正数
        int key = (sum % k + k) % k;
        if (map.containsKey(key)) ans += map.get(key);
        map.put(key, map.getOrDefault(key, 0) + 1);
    }
    return ans;
}

连续的子数组和

详情可见题目 连续的子数组和

这个题目和上一个题目几乎一样，唯一不同的是「子数组大小至少为 2」，所以这个题目主要就介绍如何才可以得到大小至少为 2 的子数组

当我们处理preSum[3]的时候，只需要在前两个中搜索是否有满足条件的数据即可，即：处理i时，只需要在[0...i-2]中检索

xxxxxxxxxx
public boolean checkSubarraySum(int[] nums, int k) {
    int[] preSum = new int[nums.length + 1];
    for (int i = 1; i < preSum.length; i++) preSum[i] = preSum[i - 1] + nums[i - 1];
    Set<Integer> set = new HashSet<>();
    for (int i = 2; i < preSum.length; i++) {
        int key = preSum[i - 2] % k;
        set.add(key);
        if (set.contains(preSum[i] % k)) return true;
    }
    return false;
}

为什么这个题目没有加一行set.add(0)代码呢？

观察代码可知，我们是先add后检索。当i = 2时，preSum[i - 2] = preSum[0] = 0，所以我们已经提前把 0 加入set集合中了

滑动窗口解决子数组问题

关于「滑动窗口技巧」的详细介绍可见 滑动窗口技巧

这一类「子数组问题」存在两个共同的特点：

• 处理子数组中单个元素 (研究对象)
• 给出的限定条件为一个范围 (约束条件)，如：和>=target的子数组 或者 乘积严格小于k

乘积小于 K 的子数组

详情可见题目 乘积小于 K 的子数组

我们维护一个滑动窗口，保证滑动窗口内的元素乘积严格小于k。对于每一次滑动窗口右边界的更新，都需要更新一次结果

对于区间[i, j]，计算以j结尾的所有子数组数量，为j - i + 1

所以具体的代码如下：

xxxxxxxxxx
public int numSubarrayProductLessThanK(int[] nums, int k) {
    // 特殊情况提前判断
    if (k <= 1) return 0;
    int l = 0, r = 0;
    // 记录子数组的乘积
    int product = 1;
    // 记录结果
    int res = 0;
    while (r < nums.length) {
        // 扩张右边界
        product *= nums[r++];
        // 如果此时子数组乘积不满足要求，收缩左边界，始终保持子数组 [l, r] 满足题目约束条件
        while (product >= k) product /= nums[l++];
        // 更新结果，添加以 l 结尾的子数组的数量
        // 没有 +1 是因为前面已经 r++
        res += (r - l);
    }
    return res;
}

含最多 K 个可整除元素的子数组

详情可见题目 含最多 K 个可整除元素的子数组

这个题目和上面的题目基本上差不多，我们用count记录当前子数组中满足要求的元素

xxxxxxxxxx
public int countDistinct(int[] nums, int k, int p) {
    int l = 0, r = 0;
    int count = 0;
    Set<String> set = new HashSet<>();
    while (r < nums.length) {
        // 扩张右边界
        if (nums[r++] % p == 0) count++;
        // 如果此时 count 不满足要求，收缩左边界，始终保持子数组 [l, r] 内元素数量满足题目约束条件
        while (count > k) {
            if (nums[l++] % p == 0) count--;
        }
        // 记录结果
        StringBuffer sb = new StringBuffer();
        // 记录以 r 结尾的子数组数据
        // r - 1 是因为前面已经 r++
        for (int i = r - 1; i >= l; i--) {
            // 必须添加 " "，才能达到去重的效果
            // 如：1 4 和 14 如果不加 " "，就会是一样的
            sb.append(nums[i]).append(" ");
            set.add(sb.toString());
        }
    }
    return set.size();
}

长度最小的子数组

详情可见题目 长度最小的子数组

这个题目满足「前缀和解决子数组问题」的第一个特点，所以其实可以用前缀和去解决该问题

对每一个子数组元素之和进行判断，得到长度最短满足要求的子数组即可

xxxxxxxxxx
public int minSubArrayLen(int target, int[] nums) {
    int ans = Integer.MAX_VALUE;
    int[] preSum = new int[nums.length + 1];
    for (int i = 1; i < preSum.length; i++) {
        preSum[i] = preSum[i - 1] + nums[i - 1];
        // 遍历以 i 结尾的所有子数组
        for (int j = i - 1; j >= 0; j--) {
            if (preSum[i] - preSum[j] >= target) ans = Math.min(ans, i - j);
        }
    }
    return ans == Integer.MAX_VALUE ? 0 : ans;
}

是不是感觉很满意，但是看一眼执行时间！！(瞬间又不满意了)

其实这个问题也满足「滑动窗口解决子数组问题」的第一个特点，所以我们可以尝试用滑动窗口去试试！

我们维护一个滑动窗口，保证滑动窗口内的元素之和>= target时更新结果，这个问题用滑动窗口去解决的代码框架和 滑动窗口技巧 中提到的结构保持高度的一致！

xxxxxxxxxx
public int minSubArrayLen(int target, int[] nums) {
    int l = 0, r = 0;
    int sum = 0;
    int res = Integer.MAX_VALUE;
    while (r < nums.length) {
        sum += nums[r++];
        // 子数组中元素之和 >= target 开始更新结果，同时收缩窗口
        while (sum >= target) {
            // 此循环内的所有子数组之和均满足要求，所以每次收缩都更新一次结果
            res = Math.min(res, r - l);
            sum -= nums[l++];
        }
    }
    return res == Integer.MAX_VALUE ? 0 : res;
}

同样的，我们来看看执行的时间 (有了质的进步)

动态规划解决子数组问题

关于「动态规划解题套路框架」的详细介绍可见 动态规划解题套路框架

这一类「子数组问题」存在一个共同的特点：

• 求最值问题，如：最大子数组和、乘积最大子数组等

最大子数组和

详情可见题目 最大子数组和

根据动态规划的思维框架：明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义，我们一步一步的分析

首先抽象出原问题「对于数组num[0..n]，找出一个以num[n]结尾的最大和的连续子数组」，所以对应的子问题是「对于数组num[0..i]，找出一个以num[i]结尾的最大和的连续子数组」

而「状态」是原问题和子问题中会发生变化的变量，所以「状态」即为nums[0..i]

再来确定「选择」，「选择」是导致「状态」产生变化的行为，即：选择nums[i]接着nums[0..i-1]继续求和，或者从nums[i]开始重新求和

根据「状态」和「选择」，我们可以给出dp[]的定义：dp[i]表示以nums[i]结尾的子数组的最大和

现在，我们也可以很快确定 base case，即：dp[0] = 0

具体实现代码如下：

xxxxxxxxxx
public int maxSubArray(int[] nums) {
    int[] dp = new int[nums.length + 1];
    // 防止只有负数的情况
    int res = nums[0];
    for (int i = 1; i < dp.length; i++) {
        // 如果 dp[i - 1] < 0，无论如何加上 nums[i - 1]，结果只会更小
        if (dp[i - 1] < 0) dp[i] = nums[i - 1];
        else dp[i] = dp[i - 1] + nums[i - 1];
        res = Math.max(res, dp[i]);
    }
    return res;
}

由于dp[i]只和dp[i-1]有关，所以我们还可以对空间复杂度优化一波，代码如下：

xxxxxxxxxx
public int maxSubArray(int[] nums) {
    int dp = 0;
    // 防止只有负数的情况
    int res = nums[0];
    for (int i = 0; i < nums.length; i++) {
        // 如果 dp[i - 1] < 0，无论如何加上 nums[i - 1]，结果只会更小
        if (dp < 0) dp = nums[i];
        else dp = dp + nums[i];
        res = Math.max(res, dp);
    }
    return res;
}

乘积最大子数组

详情可见题目 乘积最大子数组

对于「动态规划解决子数组问题」，「状态」和「选择」都大差不差，唯一有区别是dp数组的定义

根据经验，对于子数组的问题中，dp[i]定义最多的就是以i结尾的满足题目条件的最值。例如本题，dp[]的定义如下：dp[i]表示以nums[i]结尾的乘积最大的子数组

我们现在需要考虑的就是「状态转移方程」

情况一：如果nums[i] > 0

• 如果 dp[i - 1] > 0，那么dp[i] = dp[i - 1] * nums[i]
• 如果 dp[i - 1] < 0，那么dp[i] = nums[i]
• 综上：dp[i] = Math.max(dp[i - 1] * nums[i], nums[i])

情况二：如果nums[i] < 0，我们需要的是以nums[i - 1]结尾的乘积最小的子数组，记为iMin[i - 1] (原因：一个负数✖️最小值，才能变得更大)

• 如果 iMin[i - 1] > 0，那么iMin[i] = nums[i]
• 如果 iMin[i - 1] < 0，那么iMin[i] = iMin[i - 1] * nums[i]
• 综上：iMin[i] = Math.max(iMin[i - 1] * nums[i], nums[i])

经过上面的分析，我们发现只有一个存储以nums[i]结尾的乘积最大的子数组是不够的，所以我们更新一下dp数组的定义

iMax[]的定义如下：iMax[i]表示以nums[i]结尾的乘积最大的子数组

iMin[]的定义如下：iMin[i]表示以nums[i]结尾的乘积最大的子数组

同样的，由于iMax[i]只和iMax[i-1]有关，所以我们还可以对空间复杂度优化一波，代码如下：

xxxxxxxxxx
public int maxProduct(int[] nums) {
    // 防止只有负数的情况
    int res = nums[0];
    int iMax = 1, iMin = 1;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] < 0) {
            int tmp = iMax;
            iMax = iMin;
            iMin = tmp;
        }
        iMax = Math.max(iMax * nums[i], nums[i]);
        iMin = Math.min(iMin * nums[i], nums[i]);
        res = Math.max(res, iMax);
    }
    return res;
}

最长重复子数组

详情可见题目 最长重复子数组

同理，「状态」和「选择」都大差不差，唯一有区别是dp数组的定义

根据经验，对于子数组的问题中，dp[i]定义最多的就是以i结尾的满足题目条件的最值。例如本题，dp[][]的定义如下：dp[i][j]表示以nums1[i]和nums2[j]结尾的最长重复子数组

如果nums1[i] != nums2[j]，那么以它俩结尾的重复子数组长度为 0

如果nums1[i] == nums2[j]，那么就需要看以nums1[i - 1]和nums2[j - 1]结尾的最长重复子数组的长度，然后➕1 即可

状态转移如下图所示：

所以就可以很容易的写出代码：

public int findLength(int[] nums1, int[] nums2) {
    int[][] dp = new int[nums1.length + 1][nums2.length + 1];
    int res = 0;
    for (int i = 1; i < dp.length; i++) {
        for (int j = 1; j < dp[0].length; j++) {
            if (nums1[i - 1] == nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
            res = Math.max(res, dp[i][j]);
        }
    }
    return res;
}