常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）

零、常用枚举技巧。

0.1、维护左，枚举右

对于双变量问题，例如两数之和$a_i + a_j = t$， 可以枚举右边$a_j$，转化成单变量问题，也就是$a_j$左边是否有$a_i=t-a_j$，这可以用哈希表维护。

1. 两数之和（20251010）

Details

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

提示：

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• 只会存在一个有效答案

**进阶：**你可以想出一个时间复杂度小于 O(n2) 的算法吗？

题目要求：从数组中找到两个元素相加和等于target，数学表达式就是：

$$nums[i] + nums[j] = target, (i < j)$$

换个思路，我们遍历数组，在哈希表中查找target - nums[i]，就能得到：

$$nums[i] = target - nums[j], (i<j)$$

即问题变成：在一些数中找一个数。（哈希表非常适合做这件事）。

Java

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int x = nums[i];
            int y = target - x;
            // 如果哈希表里面存在target-x的值就返回
            if (cnt.containsKey(y)) {
                return new int[] { cnt.get(y), i };
            }
            // 否则的话，就把这个值存到哈希表里面。
          	// 是将元素维护到哈希表中，不是将相减后的元素存在哈希表中
            cnt.put(x, i);
        }
        return new int[2];
    }
}

0.2、枚举中间

对于三个或者四个变量的问题，枚举中间的变量往往更好算。

为什么？比如问题有三个下标，需要满足$0<=i<j<k<n$，对比一下：

• 枚举 i， 后续计算中还需要保证$j<k$
• 枚举 j， 那么i和k自动被j隔开，互相独立，后续计算中无需关心i和k的位置关系

所以枚举中间的变量更简单。

2909. 元素和最小的山形三元组 II（20251010）

Details

给你一个下标从 0 开始的整数数组 nums 。

如果下标三元组 (i, j, k) 满足下述全部条件，则认为它是一个 山形三元组 ：

• i < j < k
• nums[i] < nums[j] 且 nums[k] < nums[j]

请你找出 nums 中 元素和最小 的山形三元组，并返回其 元素和 。如果不存在满足条件的三元组，返回 -1 。

示例 1：

输入：nums = [8,6,1,5,3]
输出：9
解释：三元组 (2, 3, 4) 是一个元素和等于 9 的山形三元组，因为： 
- 2 < 3 < 4
- nums[2] < nums[3] 且 nums[4] < nums[3]
这个三元组的元素和等于 nums[2] + nums[3] + nums[4] = 9 。可以证明不存在元素和小于 9 的山形三元组。

示例 2：

输入：nums = [5,4,8,7,10,2]
输出：13
解释：三元组 (1, 3, 5) 是一个元素和等于 13 的山形三元组，因为： 
- 1 < 3 < 5 
- nums[1] < nums[3] 且 nums[5] < nums[3]
这个三元组的元素和等于 nums[1] + nums[3] + nums[5] = 13 。可以证明不存在元素和小于 13 的山形三元组。

示例 3：

输入：nums = [6,5,4,3,4,5]
输出：-1
解释：可以证明 nums 中不存在山形三元组。

提示：

• 3 <= nums.length <= 105
• 1 <= nums[i] <= 108

枚举中间的数。

枚举nums[j]，我们需要求出j左边所有元素的最小值和右边所有元素的最小值。

这可以递推计算。定义suf[i]表示从nums[i]到nums[n-1]的最小值（最小后缀），则有：

$$suf[i] = min(suf[i+1], nums[i])$$

前缀最小值pre的计算方式同理，可以和答案一起算，所以只需要一个变量。

那么答案就是$pre + nums[i] + suf[i+1]$的最小值。

Java

class Solution {
    public int minimumSum(int[] nums) {
        int n = nums.length;

        int[] suf = new int[n];
        suf[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            suf[i] = Math.min(suf[i + 1], nums[i]);
        }

        int ans = Integer.MAX_VALUE;
        int pre = nums[0];

        for (int i = 1; i < n - 1; i++) {
            int x = nums[i];
            if (pre < x && x > suf[i + 1]) {
                ans = Math.min(ans, pre + x + suf[i + 1]);
            }
            pre = Math.min(pre, x);
        }
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}

0.3、遍历对角线

3446. 按对角线进行矩阵排序

略

一、前缀和

1.1、基础

左闭右开公式：下标为左闭右开区间$[left, right)$的元素和就是$sum[right]-sum[left]$.

303. 区域和检索 - 数组不可变（20251010）

Details

给定一个整数数组 nums，处理以下类型的多个查询:

1. 计算索引 left 和 right （包含 left 和 right）之间的 nums 元素的 和 ，其中 left <= right

实现 NumArray 类：

• NumArray(int[] nums) 使用数组 nums 初始化对象
• int sumRange(int i, int j) 返回数组 nums 中索引 left 和 right 之间的元素的 总和 ，包含 left 和 right 两点（也就是 nums[left] + nums[left + 1] + ... + nums[right] )

示例 1：

输入：
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
输出：
[null, 1, -1, -3]

解释：
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3)
numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1)) 
numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))

因为是求$[left, right]$之间的和，$s[left]$表示$nums[0, left-1]$的和，$s[right]$表示$nums[0, right-1]$的和。

所以就是$s[right+1] - s[left]$

（上面的perSum就是定义的前缀数组s。）

问：为什么要定义s[0]=0，这样做有什么好处？ 如果$left=0$， 要计算的就是下标从$nums[0]$到$nums[right]$，按照公式，我们要用$s[right+1]-s[0]$，如果不定义$s[0]=0$，就必须特判$left=0$的情况

Java

class NumArray {
    // 定义数组s，s[i]表示前i-1个数的和
    private final int[] s;
    public NumArray(int[] nums) {
        // 前缀和数组的长度需要+1，来保存s[0] =0
        s = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            s[i + 1] = s[i] + nums[i];
        }
    }
    public int sumRange(int left, int right) {
        // left right是在nums中的下标
        // [left, right]的和
        return s[right + 1] - s[left];
    }
}

2559. 统计范围内的元音字符串数（20251011）

Details

给你一个下标从 0 开始的字符串数组 words 以及一个二维整数数组 queries 。

每个查询 queries[i] = [li, ri] 会要求我们统计在 words 中下标在 li 到 ri 范围内（包含 这两个值）并且以元音开头和结尾的字符串的数目。

返回一个整数数组，其中数组的第 i 个元素对应第 i 个查询的答案。

**注意：**元音字母是 'a'、'e'、'i'、'o' 和 'u' 。

示例 1：

输入：words = ["aba","bcb","ece","aa","e"], queries = [[0,2],[1,4],[1,1]]
输出：[2,3,0]
解释：以元音开头和结尾的字符串是 "aba"、"ece"、"aa" 和 "e" 。
查询 [0,2] 结果为 2（字符串 "aba" 和 "ece"）。
查询 [1,4] 结果为 3（字符串 "ece"、"aa"、"e"）。
查询 [1,1] 结果为 0 。
返回结果 [2,3,0] 。

示例 2：

输入：words = ["a","e","i"], queries = [[0,2],[0,1],[2,2]]
输出：[3,2,1]
解释：每个字符串都满足这一条件，所以返回 [3,2,1] 。

提示：

• 1 <= words.length <= 105
• 1 <= words[i].length <= 40
• words[i] 仅由小写英文字母组成
• sum(words[i].length) <= 3 * 105
• 1 <= queries.length <= 105
• 0 <= queries[j][0] <= queries[j][1] < words.length

读了半天题才读懂，就是对每个queries元素，计算words下标在[queries[i][0], queries[i][1]]之间的元音字母开头和结尾的字符串的个数。

Java

class Solution {
    public int[] vowelStrings(String[] words, int[][] queries) {
        // 计算前缀和数组
        int n = words.length;
        int[] cnt = new int[n + 1];
        for (int i = 0; i < n; i++) {
            int x = isVowelString(words[i]) == true ? 1 : 0;
            cnt[i + 1] = cnt[i] + x;
        }
        // 维护结果
        int[] ans = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int[] row = queries[i];
            ans[i] = cnt[row[1] + 1] - cnt[row[0]];
        }
        return ans;
    }

    public boolean isVowelString(String s) {
        // 判断字符串开头结尾的字符是否都是元音
        return isVowelLetter(s.charAt(0)) && isVowelLetter(s.charAt(s.length() - 1));
    }
    
    public boolean isVowelLetter(char c) {
        // 判断字符是否是元音
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }
}

1.2、前缀和与哈希表

通常要用到「枚举右，维护左」的技巧。

560. 和为 K 的子数组（20251011）

Details

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

子数组是数组中元素的连续非空序列。

示例 1：

输入：nums = [1,1,1], k = 2
输出：2

示例 2：

输入：nums = [1,2,3], k = 3
输出：2

提示：

• 1 <= nums.length <= 2 * 104
• -1000 <= nums[i] <= 1000
• -107 <= k <= 107

子数组是数组中元素的连续非空序列。

理解就是求子数组的和等于k，这个很容易想到前缀和，计算$s[j] - s[i] = k, (i < j)$，在借鉴两数之和的思路来求解。

灵神的题解还有没有搞懂的，这里链接一下：前缀和+哈希表：从两次遍历到一次遍历

class Solution {
    public int subarraySum(int[] nums, int k) {
        // 前缀和 + 维护左，枚举右

        // 维护前缀和数组
        int n = nums.length;
        int[] s = new int[n + 1];
        for (int i = 0; i < n; i++) {
            s[i + 1] = s[i] + nums[i];
        }
        // 维护左，枚举右
        int ans = 0;
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int j = 0; j < s.length; j++) {
            // i < j, s[j] - s[i] = k
            // 因为是从左往右枚举的，所有cnt中存的都是较小的数, s[i] = s[j] - k
            int t = s[j] - k;
            ans += cnt.getOrDefault(t, 0);
            cnt.merge(s[j], 1, Integer::sum);
        }
        return ans;
    }
}

二、单调栈

今天了解到一个新的有用的解题数据结构，单调栈， 下面来具体学习一下。

设计到的相关题目：

496. 下一个更大元素 I

503. 下一个更大元素 II

739. 每日温度

42. 接雨水

1793. 好子数组的最大分数

下一个更高温度出现在几天后？ [1,1,0,0]

下一个更高温度是多少度？[60, 70, 0, 0]

三、并差集

Disjoint Set 并查集

图中是否有环

压缩轮径

find

Union

547. 省份数量

class Solution {
    public int findCircleNum(int[][] isConnected) {

        int n = isConnected.length;
        UnionFind uf = new UnionFind(n);
        for(int i =0;i<n;i++){
            for(int j = i;j<n;j++){
                if(isConnected[i][j] == 1){
                    uf.union(i, j);
                }
            }
        }
        return uf.size;
    }


}

class UnionFind{
    int[] roots;
    int size;// 连通图的个数
    public UnionFind(int n){
        roots = new int[n];
        size = n;
        for(int i =0;i<n;i++){
            roots[i] = i;
        }
    }
    public int find(int i){
        if(i == roots[i]){
            return i;
        }
        roots[i] = find(roots[i]);
        return roots[i];
    }
    public void union(int x, int y){
        int xroot = find(x);
        int yroot = find(y);
        if ( xroot == yroot){
            return;
        }
        roots[yroot] = xroot;
        size--;
    }
}