在 LeetCode 上练习时了解到，并查集 这一数据结构比较常用于解决图论方面的问题，其应用场景与搜索有很多重叠。例如，两者都可用于求无向图中连通分量 （connected component or just component）的个数。下图1中就有三个连通分量，分别以不同颜色标出： LeetCode 例题：547. 省份数量 并查集 鉴于 STL 没有实现并查集（已知 Boost 有），我们需要自己动手实现：以 vector<int> 为本体，辅以 get_root() 和 merge_set() 两个函数，即可完成。注意，此实现舍弃了性能的完整性2，追求的目标是代码量小、功能够用，适用于做题和笔试场景。 值得注意的 …

注：双指针法俗称“滑动窗口”，但我不喜欢这个名称，因为这给人感觉是一个固定长度的窗口在（数组上）滑动，而实际上该方法中的“窗口”长度不是固定的，更像个手风琴或弹簧。 例题 前缀+Hash：560. 和为K的子数组 给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。 示例 1 : 1输入:nums = [1,1,1], k = 2 2输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。 题解： 1class Solution { 2public: 3 int subarraySum(vector<int>& nums, int k) { 4 …

概念 数列 $a$，$b$ 满足以下条件： $$ \begin{align*} b_1 &= a_1\\ b_2 &= a_2 - a_1\\ &\vdots\\ b_n &= a_n - a_{n-1} \end{align*} $$ 故有： $$ \begin{align*} a_1 &= b_1\\ a_2 &= b_1 + b_2\\ &\vdots\\ a_n &= b_1 + b_2 + \cdots + b_n \end{align*} $$ 其中称 $b$ 为 $a$ 的差分（Difference Array），$a$ 为 $b$ 的前缀和（Prefix Sum Array）。两者为一组逆运算。 用法 差分数列的一个 …