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

零、常用枚举技巧。

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]$$

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

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. 按对角线进行矩阵排序

略

一、前缀和

最近在刷力扣的时候，有一道题：14. 最长公共前缀， 可以用 python3 的特殊 api 来求解，像是用 zip 函数，将可迭代对象对应的元素打包成一个个元组，然后返回元组组成的列表。我们就可以根据元组的长度来判断是否前缀是否相同。

比如zip(['flower', 'flow', 'flight']) 返回的结果是[('f', 'f', 'f'),('l', 'l', 'l'),('o', 'o', 'i'),('w', 'w', 'g')]

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        ans = zip(*strs)  # List[Tuple]
        s = ''
        for i in ans:
            if len(set(i)) == 1:
                s += i[0]
            else:
                break  # 后面能匹配上也不要了
        return s

但是看很多题解都是使用 trie 树来求解的，这里就来仔细的学习了解一下。 参考 labuladong 网站文章： 前缀树算法模板秒杀五道算法题

真的是，前面的回溯算法还没有看，这有来一个前缀和的算法，难受。

原文章地址：小而美的算法技巧：前缀和数组

简单理解，就是用前面已经算好的前缀加上当前元素的值作为当前元素的前缀和，比如 nums = [2,3,5,1],

preSum = [2, ....]， 只算出来第一个值，这个时候要算第二个值的话，就可以用 preSum[i-1] + nums[i]来计算。

class NumArray {
    private int[] preSum;

    public NumArray(int[] nums) {
        preSum = new int[nums.length+1];
        for(int i=1;i<preSum.length;i++){
            preSum[i] = preSum[i-1] + nums[i-1];  // 为啥是i-1， 因为是从i开始的，方便计算总和
        }
    }
    public int sumRange(int left, int right) {
        return preSum[right+1] - preSum[left];  // 为什么是right+1?因为要取到right这个值， 为什么不去到left？因为要留下left对应的值
    }
}

20240318 更新

今天力扣的每日一题是关于前缀和的，正好来更新一下自己关于前缀和的知识储备。

还是上面说的那一道题。如果我们用常规的方法的话，我们需要再 sumRange 里面定义一个循环来求 nums[left] 到 nums[right]之间的和。

前缀和正好就是求数组某一段的和。我们来仔细阅读一下上面的解题代码。

private int[] preSum;
public NumArray(int[] nums) {
	preSum = new int[nums.length+1];
}

定义一个 perSum 的数组，用来存放每个位置的前缀和，perSum 的长度比 num 的长度长一位，用来存放 0.

for(int i=1;i<preSum.length;i++){
	preSum[i] = preSum[i-1] + nums[i-1];
}

理解 perSum[0] = 0 是 base case，后面的 perSum[i] 就根据前面的 perSum[i-1] 和 nums[i-1] 来计算， 这里很好理解，就是根据前面一个 perSum 和 perSum[i]对应的 nums 来计算，因为 perSum 和 nums 有一个下标偏移。

public int sumRange(int left, int right) {
	return preSum[right+1] - preSum[left];
}

最后取[left, right]之间的和下标为什么取 right+1, 左边为什么不加一？

这里的 left 和 right 是相对于 nums 来说的，我们要在 perSum 里面计算，他们两个有一个下标的偏移，所以这里 right 要取 right+1。

left 的话，因为也是闭区间，left 下标的值也是要取到，如果是 left+1 的话，就把 left 也减掉了。

LCR 010. 和为 K 的子数组

给定一个整数数组和一个整数 k，请找到该数组中和为 k 的连续子数组的个数

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

前缀和+哈希解决。

维护列表的前缀和数组 pre，我们只需要在 pre 里面找到 pre[i]-k 的值有多少个，就是最后返回的结果。

class Solution {
    public int subarraySum(int[] nums, int k) {
        int n = nums.length, ans = 0;
        int[] pre = new int[n+1];
        for(int i = 1;i<pre.length;i++){
            pre[i] = pre[i-1] + nums[i-1];
        }
        HashMap<Integer, Integer> mp = new HashMap<>();
        mp.put(0, 1);
        for(int i = 1;i<pre.length;i++){
            int dif = pre[i] - k;
            // 看mp里面有几个dif
            ans += mp.getOrDefault(dif, 0);
            // 更新mp中pre[i]的个数 pre[i]有几个 pre[i]-k就有几个
            mp.put(pre[i], mp.getOrDefault(pre[i], 0)+1);
        }
        return ans;
    }
}

1.1、基础

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

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

Details

Java

class NumArray {
    private final int[] s;

    public NumArray(int[] nums) {
        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) {
        return s[right + 1] - s[left];
    }
}

二、单调栈

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

设计到的相关题目：

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--;
    }
}

Changelog

10/10/25, 3:04 PM

View All Changelog

• 1ee1e-feat(wiki): algo -on 10/10/25