子数组子串

通常考虑滑窗

子数组最大和/积

53. 最大子数组和 mid

剑指 Offer 42. 连续子数组的最大和

给你一个整数数组 nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

记录以当前元素为结束元素的子数组的最大和, 即可 DP

DP

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int[] sum = new int[n];
        int res = sum[0] = nums[0];
        for (int i = 1; i < n; i++) {
            sum[i] = nums[i] + Math.max(sum[i - 1], 0);
            res = Math.max(res, sum[i]);
        }
        return res;
    }
}

压缩

class Solution {
    public int maxSubArray(int[] nums) {
        int sum = 0;
        int res = Integer.MIN_VALUE;
        for (int e : nums) {
            sum = e + Math.max(sum, 0);
            res = Math.max(res, sum);
        }
        return res;
    }
}

分治
线段树, 可以求任意区内的最大和, 建树的过程中直接求

class Solution {
    static class Node {
        int lSum, rSum, max, sum;

        Node(int lSum, int rSum, int max, int sum) {
            this.lSum = lSum; // 包含左端点最大和
            this.rSum = rSum; // 包含右端点最大和
            this.max = max;   // 最大和
            this.sum = sum;   // 和
        }
    }

    public int maxSubArray(int[] nums) {
        return getSum(nums, 0, nums.length - 1).max;
    }

    public Node getSum(int[] a, int l, int r) {
        if (l == r) return new Node(a[l], a[l], a[l], a[l]);
        int m = l + (r - l >> 1);
        Node lSub = getSum(a, l, m);
        Node rSub = getSum(a, m + 1, r);
        return merge(lSub, rSub);
    }

    public Node merge(Node l, Node r) {
        int sum = l.sum + r.sum;
        int lSum = Math.max(l.lSum, l.sum + r.lSum);
        int rSum = Math.max(r.rSum, r.sum + l.rSum);
        int max = Math.max(Math.max(l.max, r.max), l.rSum + r.lSum);
        return new Node(lSum, rSum, max, sum);
    }
}

152. 乘积最大子数组 mid

给你一个整数数组 nums，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

测试用例的答案是一个 32-位 整数。

子数组 是数组的连续子序列。

DP

与 和最大和子数组 类似, 保存以 i 为结尾的最大积和最小积
最大积要在线求 $max=max(maxdp[pre]\ast curr,mindp[pre]\ast curr,curr)$

class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        int[] maxA = new int[n];
        int[] minA = new int[n];
        maxA[0] = nums[0];
        minA[0] = nums[0];
        int ans = maxA[0];
        for (int i = 1; i < n; ++i) {
            maxA[i] = Math.max(maxA[i - 1] * nums[i], Math.max(nums[i], minA[i - 1] * nums[i]));
            minA[i] = Math.min(minA[i - 1] * nums[i], Math.min(nums[i], maxA[i - 1] * nums[i]));
            ans = Math.max(ans, maxA[i]);
        }
        return ans;
    }
}

最小窗口

76. 最小覆盖子串 hard

LCR 017. 最小覆盖子串

给你一个字符串 s, 一个字符串 t。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 ""。

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

解法 滑动窗口

class Solution {
    public String minWindow(String s, String t) {
        int[] need = new int[128];
        for (char c : t.toCharArray()) {
            need[c]++;
        }
        // gap是需求的字符个数
        int j = 0, gap = t.length(), start = 0, size = Integer.MAX_VALUE;
        char[] arr = s.toCharArray();
        for (int i = 0; i < arr.length; i++) {
            if (need[arr[i]] > 0) gap--;
            need[arr[i]]--;
            // 缩
            if (gap == 0) {
                while (need[arr[j]] < 0) {
                    need[arr[j]]++;
                    j++;
                }
                if (i - j + 1 < size) {
                    size = i - j + 1;
                    start = j;
                }
            }
        }
        return size == Integer.MAX_VALUE ? "" : s.substring(start, start + size);
    }
}

209. 长度最小的子数组 mid

LCR 008. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

解法 滑动窗口

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int l = 0;
        int sum = 0;
        int res = n + 1;
        for (int r = 0; r < n; r++) {
            sum += nums[r];
            // 缩窗
            while (sum - nums[l] >= target) {
                sum -= nums[l++];
            }
            if (sum >= target) res = Math.min(res, r - l + 1);
        }
        return res == n + 1 ? 0 : res;
    }
}

581. 最短无序连续子数组 mid

给你一个整数数组 nums，你需要找出一个 连续子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。

请你找出符合题意的 最短 子数组，并输出它的长度。

可以暴力排序, 然后按索引比较
需要参与排序的范围, $nums[\mathrm{右}\mathrm{边}\mathrm{界}+1]>max(\mathrm{左}\mathrm{边}),nums[\mathrm{左}\mathrm{边}\mathrm{界}-1]<max(\mathrm{右}\mathrm{边})$
就可以 从左到右找右边界, 从右到左找左边界

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int n = nums.length;
        int l = -1, r = -2;
        int max = nums[0];
        int min = nums[n - 1];
        for (int i = 0; i < n; i++) {
            // 从左到右, 找右边界
            if (nums[i] < max) r = i;
            else max = nums[i];
            // 从右到左, 找左边界
            if (nums[n - 1 - i] > min) l = n - 1 - i;
            else min = nums[n - 1 - i];
        }
        return r - l + 1;
    }
}

697. 数组的度 easy

给定一个非空且只包含非负数的整数数组 nums，数组的 度 的定义是指数组里任一元素出现频数的最大值。

你的任务是在 nums 中找到与 nums 拥有 相同的度 的最短连续子数组，返回其长度。

找到每个元素的度和左右范围

class Solution {
    public int findShortestSubArray(int[] nums) {
        Map<Integer, int[]> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int[] val = map.putIfAbsent(nums[i], new int[]{1, i, i});
            if (val != null) {
                val[0]++;
                val[2] = i;
            }
        }
        int res = 0;
        int max = 0;
        for (Map.Entry<Integer, int[]> e : map.entrySet()) {
            int[] val = e.getValue();
            if (max < val[0]) {
                max = val[0];
                res = val[2] - val[1] + 1;
            } else if (max == val[0]) {
                res = Math.min(res, val[2] - val[1] + 1);
            }
        }
        return res;
    }
}

窗口内最大值

需要一种数据结构, 维护窗口内的最大值
优先考虑单调队列

滑动窗口
开窗可以在滑动中先 while;
缩窗可以在求值前, 也可以在求值后, 如果求值后不需要写 if 就写在求值后(通常需要维护一个 left)

239. 滑动窗口最大值 hard

剑指 Offer 59 - I. 滑动窗口的最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回 滑动窗口中的最大值。

解法 1 优先队列 实时维护(超时)

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        PriorityQueue<Integer> que = new PriorityQueue<>((a, b) -> b - a);
        int[] res = new int[n - k + 1];
        for (int l = 0, r = 0; r < n; r++, l++) {
            while (--k > 0) {
                que.add(nums[r++]);
            }
            que.add(nums[r]);
            res[l] = que.element();
            que.remove(nums[l]);
        }
        return res;
    }
}

解法 2 有序集合

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] res = new int[n - k + 1];
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int l = 0, r = 0; r < n; r++, l++) {
            // 开窗
            while (--k > 0) {
                map.merge(nums[r++], 1, Integer::sum);
            }
            // 滑动
            map.merge(nums[r], 1, Integer::sum);
            // 取值
            res[l] = map.lastKey();
            // 缩窗
            if (map.get(nums[l]) == 1) map.remove(nums[l]);
            else map.merge(nums[l], -1, Integer::sum);
        }
        return res;
    }
}

解法 3 优先队列 惰性维护

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        PriorityQueue<int[]> que = new PriorityQueue<>((a, b) -> a[0] != b[0] ? b[0] - a[0] : b[1] - a[1]);
        int[] res = new int[n - k + 1];
        for (int r = 0; r < n; r++) {
            for (; r < k - 1; r++) {
                que.add(new int[]{nums[r], r});
            }
            que.add(new int[]{nums[r], r});
            // 堆顶元素过期才删
            while (r - que.element()[1] >= k) {
                que.remove();
            }
            res[r - k + 1] = que.element()[0];
        }
        return res;
    }
}

解法 4 单调队列

单调队列为什么可行?
单调队列非常适合处理滑窗内的极值, 对于单调减区间[s,e], 移除小于元素 e 的元素不会影响区间的最大值

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] res = new int[n - k + 1];
        Deque<Integer> que = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!que.isEmpty() && nums[que.getLast()] <= nums[i]) {
                que.removeLast();
            }
            que.addLast(i);
            // 队首已经离开窗口了
            if (i - que.getFirst() >= k) {
                que.removeFirst();
            }
            if (i >= k - 1) {
                res[i - k + 1] = nums[que.getFirst()];
            }
        }
        return res;
    }
}

其他解法 线段数 稀疏表等

能否由子串组成

139. 单词拆分 mid

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

解法 1 DP

dp[i]: s[0,i] 是否由子串构成

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        Set<String> set = new HashSet<>(wordDict);
        boolean[] dp = new boolean[n + 1]; // 右侧开区间
        dp[0] = true;
        for (int i = 0; i < n; i++) { // 右端点
            for (int j = 0; j <= i; j++) { // 左端点
                if (dp[j] && set.contains(s.substring(j, i + 1))) {
                    dp[i + 1] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
}

解法 2 DFS

DFS 搜到一段后递归搜下一段
可以记忆化剪枝, 记录哪些 start 不可用
substring 太慢, startWith 更好

class Solution {

    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] memo = new boolean[s.length() + 1];
        Arrays.fill(memo, true);
        return dfs(s, wordDict, 0, memo);
    }

    boolean dfs(String s, List<String> wordDict, int start, boolean[] memo) {
        if (start == s.length()) return true;
        if (!memo[start]) return false;
        for (String word : wordDict) {
            if (s.startsWith(word, start)) {
                if (dfs(s, wordDict, start + word.length(), memo)) {
                    return true;
                }
            }
        }
        memo[start] = false;
        return false;
    }
}

子数组数量

413. 等差数列划分 mid

如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。

• 例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。

给你一个整数数组 nums ，返回数组 nums 中所有为等差数组的 子数组 个数。

子数组 是数组中的一个连续序列。

解法 1 滑动窗口

找到每个最长等差数列, 如果等差数列长度为 n, 那么子数组数量为 1+...+(n-2)
n=3, cnt=1; n=4, cnt=1+2

class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        if (nums.length < 3) return 0;
        int res = 0;

        int gap = nums[1] - nums[0];
        int cnt = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] - nums[i - 1] == gap) {
                cnt++;
                continue;
            }
            // 计算前一段
            res += sum(cnt);
            gap = nums[i] - nums[i - 1];
            cnt = 2;
        }
        res += sum(cnt);
        return res;
    }

    private int sum(int n) {
        int sum = 0;
        for (int i = 1; i <= n - 2; i++) {
            sum += i;
        }
        return sum;
    }
}

解法 2 DP

dp[i]: 以 nums[i] 为结尾的新增数列数量

dp[2] = 1
    [0, 1, 2]

dp[3] = dp[2] + 1 = 2
    [0, 1, 2, 3], // [0, 1, 2] 之后加一个 3
    [1, 2, 3]     // 新的递增子区间

dp[4] = dp[3] + 1 = 3
    [0, 1, 2, 3, 4], // [0, 1, 2, 3] 之后加一个 4
    [1, 2, 3, 4],    // [1, 2, 3] 之后加一个 4
    [2, 3, 4]        // 新的递增子区间

class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        if (nums.length < 3) return 0;
        int[] dp = new int[nums.length];

        int res = 0;
        for (int i = 2; i < nums.length; i++) {
            if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) {
                dp[i] = dp[i - 1] + 1;
                res += dp[i];
            }
        }
        return res;
    }
}

560. 和为 K 的子数组 mid

LCR 010. 和为 K 的子数组

给你一个整数数组 nums 和一个整数 k，请你统计并返回 该数组中和为 k 的连续子数组的个数。

解法 前缀和

迭代过程中, 只要知道前面跟 sum-target 相等的前缀和的数量, 即可$O(n)$

class Solution {
    public int subarraySum(int[] nums, int k) {
        int sum = 0;
        int res = 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        for (int num : nums) {
            sum += num;
            res += map.getOrDefault(sum - k, 0);
            map.merge(sum, 1, Integer::sum);
        }
        return res;
    }
}

647. 回文子串 mid

LCR 020. 回文子串

给你一个字符串 s，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

解法 1 中心拓展

class Solution {
    public int countSubstrings(String s) {
        int sum = 0;
        for (int i = 0; i < s.length(); i++) {
            sum += len(s, i);
        }
        return sum;
    }

    private int len(String s, int idx) {
        int cnt = 0;
        int p1 = idx, p2 = idx;
        while (p1 >= 0 && p2 < s.length()) {
            if (s.charAt(p1--) == s.charAt(p2++)) cnt++;
            else break;
        }
        p1 = idx;
        p2 = idx + 1;
        while (p1 >= 0 && p2 < s.length()) {
            if (s.charAt(p1--) == s.charAt(p2++)) cnt++;
            else break;
        }
        return cnt;
    }
}

解法 2 manacher

class Solution {
    public int countSubstrings(String s) {
        if (s.isEmpty()) return 0;
        StringBuilder sb = new StringBuilder("^#");
        for (char c : s.toCharArray()) {
            sb.append(c).append("#");
        }
        sb.append("$");
        char[] arr = sb.toString().toCharArray();
        int n = arr.length;
        int[] arm = new int[n];
        int core = 0, right = 0;
        int res = s.length();
        for (int i = 1; i < n - 1; i++) { // i 是每个串的中心
            int j = 2 * core - i; // i 关于 core 的对称点
            if (i < right) arm[i] = Math.min(right - i, arm[j]); // 镜像 arm[i]
            while (arr[i + arm[i] + 1] == arr[i - arm[i] - 1]) arm[i]++;
            if (i + arm[i] > right) {
                core = i;
                right = i + arm[i];
            }
            res += arm[i] / 2;
        }
        return res;
    }
}

696. 计数二进制子串 easy

给定一个字符串 s，统计并返回具有相同数量 0 和 1 的非空（连续）子字符串的数量，并且这些子字符串中的所有 0 和所有 1 都是成组连续的。

重复出现（不同位置）的子串也要统计它们出现的次数。

解法 1 中心扩展

class Solution {
    public int countBinarySubstrings(String s) {
        if (s.length() < 2) return 0;

        int cnt = 0;
        for (int i = 0; i < s.length() - 1; i++) {
            int j = i;
            int k = i + 1;
            char c1 = s.charAt(j);
            char c2 = s.charAt(k);
            if (c1 == c2) continue;
            while (j >= 0 && k < s.length() && s.charAt(j) == c1 && s.charAt(k) == c2) {
                cnt++;
                j--;
                k++;
            }
        }
        return cnt;
    }
}

解法 2 计数

class Solution {
    public int countBinarySubstrings(String s) {
        int i = 0, n = s.length();
        int lastCnt = 0;
        int res = 0;
        while (i < n) {
            char c = s.charAt(i);
            int cnt = 0;
            while (i < n && s.charAt(i) == c) {
                i++;
                cnt++;
            }
            res += Math.min(cnt, lastCnt);
            lastCnt = cnt;
        }
        return res;
    }
}

713. 乘积小于 K 的子数组 mid

LCR 009. 乘积小于 K 的子数组

给你一个正整数数组 nums 和一个整数 k，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。
n > 0

解法 滑窗

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k <= 1) return 0;
        int n = nums.length, res = 0, prod = 1, l = 0;
        for (int r = 0; r < n; r++) {
            prod *= nums[r];
            while (prod >= k) {
                prod /= nums[l++];
            }
            res += r - l + 1;
        }
        return res;
    }
}

最大窗口

525. 连续数组 mid

LCR 011. 连续数组

给定一个二进制数组 nums, 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。

解法 前缀和

求和为 0 的最长子数组
找到前缀和所对应的最早索引

class Solution {
    public int findMaxLength(int[] nums) {
        int n = nums.length;
        Map<Integer, Integer> map = new HashMap<>(); // sum => idx
        map.put(0, -1);
        int sum = 0;
        int res = 0;
        for (int i = 0; i < n; i++) {
            sum += nums[i] == 0 ? -1 : 1;
            Integer idx = map.get(sum);
            if (idx != null) res = Math.max(res, i - idx);
            else map.put(sum, i);
        }
        return res;
    }
}

窗口中的元素

567. 字符串的排列 mid

LCR 014. 字符串的排列

给你两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true；否则，返回 false。

换句话说，s1 的排列之一是 s2 的 子串。

解法 1 固定窗口滑窗

在 s2 中是否存在大小为 s1 的窗口里面含有 s1 所有的字符

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length()) return false;
        int[] a1 = new int[26];
        int[] a2 = new int[26];
        for (int i = 0; i < s1.length(); i++) {
            ++a1[s1.charAt(i) - 'a'];
            ++a2[s2.charAt(i) - 'a'];
        }
        for (int l = 0, r = s1.length() - 1; r < s2.length() - 1; r++, l++) {
            if (Arrays.equals(a1, a2)) return true;
            a2[s2.charAt(l) - 'a']--;
            a2[s2.charAt(r + 1) - 'a']++;
        }
        return Arrays.equals(a1, a2);
    }
}

解法 2 缩小窗口滑窗

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        if (n > m) return false;
        int[] arr = new int[26];
        for (int i = 0; i < n; i++) {
            arr[s1.charAt(i) - 'a']--;
        }

        for (int l = 0, r = 0; r < m; r++) {
            int c = s2.charAt(r) - 'a';
            arr[c]++;
            while (arr[c] > 0) {
                // 集合相等, 元素必须严丝合缝
                arr[s2.charAt(l) - 'a']--;
                l++;
            }
            if (r - l + 1 == n) return true;
        }
        return false;
    }
}

划分

763. 划分字母区间 mid

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

解法 贪心

固定左端点, 更新右端点

class Solution {
    public List<Integer> partitionLabels(String s) {
        char[] arr = s.toCharArray();
        int[] idxs = new int[26];
        Arrays.fill(idxs, -1);
        for (int i = 0; i < arr.length; i++) {
            idxs[arr[i] - 'a'] = i;
        }
        List<Integer> res = new ArrayList<>();
        int r = 0, l = 0;
        for (int i = 0; i < arr.length; i++) {
            r = Math.max(r, idxs[arr[i] - 'a']);
            if (r == i) {
                res.add(r - l + 1);
                l = i + 1;
            }
        }
        return res;
    }
}

769. 最多能完成排序的块 mid

给定一个长度为 n 的整数数组 arr ，它表示在 [0, n - 1] 范围内的整数的排列。

我们将 arr 分割成若干 块 (即分区)，并对每个块单独排序。将它们连接起来后，使得连接的结果和按升序排序后的原数组相同。

返回数组能分成的最多块数量。

注意到值的范围
[0,k] 的最大值应在 k 位置, 只要 max==k, 说明值的分布是连续的, 就可以分割

class Solution {
    public int maxChunksToSorted(int[] arr) {
        int res = 0, max = 0;
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
            if (max == i) res++;
        }
        return res;
    }
}