算法模式：前缀和
前缀和是一种高效的数组预处理技术，用于解决区间和查询问题。其核心思想是预先计算数列前n项的累计和，生成一个前缀和数组，使得任意区间的和可以通过简单的减法运算快速获得。这种方法将每次查询的时间复杂度从O(n)降低到O(1)，代价是需要额外的O(n)空间存储前缀和。在具体应用中，例如LeetCode 303题“区域和检索 - 数组不可变”，要求对给定数组频繁执行区间求和操作。通过初始化时构建前缀和数组（其中prefix[0]为0，prefix[i]表示原数组前i-1项的和），sumRange(left, right)方法可以直接返回prefix[right+1] - prefix[left]，避免了重复遍历数组的开销。该模式特别适合数据不可变且查询密集的场景，是优化动态规划或滑动窗口等问题的常见辅助手段。掌握前缀和有助于提升算法效率，尤其在处理大数据集或实时查询时，能显著减少计算成本。
算法模式：并查集
并查集是一种用于解决动态连通性问题的数据结构，能够高效管理节点间的连接关系并快速判断任意两点是否属于同一连通分量。其核心操作包括`union`（合并两个节点所属的集合）和`connected`（查询两个节点是否连通）。初始化时每个节点自成一组，通过`parent`数组记录节点的父节点，最终形成树状结构。 判断连通性时需向上查找各自根节点并比较是否相同。为提升查询效率，可应用路径压缩技术：在查找根节点过程中，将路径上所有节点直接指向根节点，从而大幅降低后续操作的时间复杂度。文章通过图示和Java代码示例展示了并查集的基本实现，包括查找、合并、连通分量计数等功能，体现了其在处理动态集合合并与连通性查询场景下的实用性。
算法模式：子集
在上一篇文章 算法模式：回溯 介绍一种“一步三回头”、“落棋有悔”的算法模式：回溯。本篇文章，介绍一种无需“一步三回头”，无需“落棋有悔”也可以解决排列组合问题的算法模式：子集。
子集
处理子集问题
举例来说明一下这个模式：
给一组数字 [1, 5, 3]
-
我们从空集开始：
[[]] -
把第一个数
1，加到之前已经存在的集合中：[[], [1]]; -
把第二个数
5，加到之前的集合中得到：[[], [1], [5], [1,5]]; -
再加第三个数
3，则有：[[], [1], [5], [1,5], [3], [1,3], [5,3], [1,5,3]].
如果原有集合中存在重复元素，那么就需要针对这种情况特殊处理一下。流程如下：
给一组数字 [5, 1, 5]
-
先对原有集合进行排序：
[1, 5, 3] -
从空集开始：
[[]] -
把第一个数
1，加到之前已经存在的集合中：[[], [1]]; -
把第二个数
5，加到之前的集合中得到：[[], [1], [5], [1,5]]; -
处理第三个数，也是
5时需要注意：-
如果还是按照上述方案处理，那么就会得到如下结果：
[[], [1], [5], [1,5], [5], [1, 5], [5, 5], [1,5, 5]]。这里出现了重复子集：[5], [1, 5]。该方案不通过，❌ -
观察最后生成的所有子集与重复的子集，会发现重复的子集，在处理第二个数时，已经处理过
[], [1]，如果再次处理5，那么就会出现重复。所以，只需要处理在处理上一个相同的数时新增加的子集即可。上一个相同数新增的子集是[5], [1,5]，只需要在这些子集后面增加当前数字即可。这样最后的子集就是：[[], [1], [5], [1,5], [5, 5], [1,5, 5]]。方案通过 ✅
-