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

零、常用枚举技巧。

0.1、枚举右，维护左

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

0.1.1、基础

1. 两数之和

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

一、前缀和

最近在刷力扣的时候，有一道题：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;
    }
}

二、单调栈

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

设计到的相关题目：

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

8/20/25, 11:06 AM

View All Changelog

• 4c155-Merge branch 'dev1'on 8/20/25