LeetCode 新手指南：动态计数更新问题的 3 种解法

本文聚焦 LeetCode 中的动态计数更新问题，为新手详细介绍三种实用解法。动态计数更新问题常涉及对数据集中元素的增减及特定条件下计数查询，解法各有优劣。文中会阐述哈希表法的灵活高效、前缀和法的预处理优势、树状数组法的高效更新与查询特性，分析适用场景，还会结合实例说明，帮助读者理解并掌握，提升解题能力。​

一、动态计数更新问题概述​

在 LeetCode 的算法题目中，动态计数更新问题是一类常见且具有一定挑战性的题目。这类问题的核心场景通常是，给定一个初始数据集，然后会有一系列的操作，包括对数据集中的元素进行增加、删除等更新操作，同时还会穿插着一些查询操作，要求我们根据当前数据集的状态，快速计算出满足特定条件的元素数量。​

比如，可能会有这样的题目：初始时有一个空数组，之后会不断进行两种操作，一种是往数组中添加一个元素，另一种是查询当前数组中小于某个特定值的元素有多少个。像这样的问题就属于动态计数更新问题。​

这类问题考察的是我们对数据结构和算法的灵活运用能力，因为不同的解法在处理更新和查询操作时的效率各不相同，选择合适的解法能让我们更高效地解决问题。​

二、哈希表法​

（一）基本原理​

哈希表（Hash Table），也称为散列表，是一种根据关键码值（Key - value）而直接进行访问的数据结构。它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。在动态计数更新问题中，我们可以利用哈希表来存储元素出现的次数，以此实现对元素的动态计数和更新。​

当我们需要添加一个元素时，就在哈希表中找到该元素对应的键，将其值（即出现次数）加 1；如果该元素不存在于哈希表中，就为其创建一个键，并将值设为 1。当需要删除一个元素时，找到对应的键，将其值减 1，如果值减到 0，就可以将该键从哈希表中删除。而在查询满足特定条件的元素数量时，我们可以遍历哈希表，统计符合条件的元素的出现次数之和。​

（二）实例解析​

以 “给定一个整数数组，实现一个数据结构，支持以下操作：添加一个整数到数据结构中，删除一个整数（如果存在），查询数据结构中小于给定整数 x 的元素的个数” 为例。​

我们可以使用一个哈希表来存储每个整数出现的次数。添加操作时，若整数在哈希表中，次数加 1，否则添加该整数并设次数为 1。删除操作时，若整数存在，次数减 1，次数为 0 则移除。查询时，遍历哈希表的所有键，将小于 x 的键对应的次数相加，得到的结果就是查询答案。​

例如，初始哈希表为空。添加 5，哈希表变为 {5:1}；添加 3，变为 {5:1,3:1}；查询小于 4 的元素个数，遍历得到 3 小于 4，次数为 1，所以答案是 1。​

（三）优缺点及适用场景​

优点：哈希表的添加和删除操作平均时间复杂度为 O (1)，非常高效，而且实现起来相对简单直观，对于元素范围不确定或者元素较为分散的情况比较适用。​

缺点：查询操作需要遍历哈希表，时间复杂度为 O (n)，其中 n 是哈希表中不同元素的个数。当元素数量较多时，查询效率会比较低。​

适用场景：适用于更新操作频繁，而查询操作较少，或者元素数量不多的情况。​

三、前缀和法​

（一）基本原理​

前缀和（Prefix Sum）是一种重要的预处理方法，它可以帮助我们快速计算数组中某一区间的和。在动态计数更新问题中，如果元素的取值范围是确定的且相对较小，我们可以先创建一个频率数组，其中频率数组的下标表示元素的值，数组的值表示该元素出现的次数。然后通过计算前缀和数组，来快速回答查询操作。​

前缀和数组的第 i 个元素表示频率数组中从下标 0 到 i 的所有元素的和，也就是值小于等于 i 的元素的总个数。当我们需要添加或删除一个元素时，只需要更新频率数组中对应下标的值，然后重新计算前缀和数组（或者在动态更新时维护前缀和数组）。查询时，根据查询条件直接获取前缀和数组中对应位置的值即可。​

（二）实例解析​

假设元素的取值范围在 0 到 100 之间，我们来解决 “添加元素、删除元素、查询小于 x 的元素个数” 的问题。​

首先创建一个大小为 101 的频率数组 freq，初始值都为 0。添加元素 5 时，freq [5] 加 1；添加元素 3 时，freq [3] 加 1。然后计算前缀和数组 prefix，prefix [i] = prefix [i-1] + freq [i]（prefix [0] = freq [0]）。此时 prefix [3] = freq [0] + freq [1] + freq [2] + freq [3] = 1，prefix [4] = prefix [3] + freq [4] = 1 等。当查询小于 4 的元素个数时，就是 prefix [3] 的值，即 1。​

如果删除元素 3，freq [3] 减 1 变为 0，此时重新计算前缀和数组，prefix [3] 变为 0，再查询小于 4 的元素个数就是 0。​

（三）优缺点及适用场景​

优点：查询操作的时间复杂度可以达到 O (1)，非常高效，因为只需要直接访问前缀和数组中的对应位置。​

缺点：元素的取值范围必须确定且不能太大，否则频率数组和前缀和数组会占用大量的内存空间。而且更新操作不仅要更新频率数组，还可能需要重新计算前缀和数组，当元素范围较大时，更新的时间成本也会增加。​

适用场景：适用于元素取值范围确定且较小，查询操作频繁的情况。​

四、树状数组法​

（一）基本原理​

树状数组（Fenwick Tree），也称为二叉索引树，是一种能够高效进行前缀和查询和单点更新的数据结构。它通过将数组中的元素按照一定的规则组织成树的结构，从而实现了在 O (logn) 的时间复杂度内完成更新和查询操作。​

在动态计数更新问题中，我们可以将元素的值映射到树状数组的索引上。当添加一个元素时，就对树状数组中对应索引的位置进行加 1 操作；删除一个元素时，进行减 1 操作。查询小于 x 的元素个数时，就查询树状数组中索引从 1 到 x-1 的前缀和（假设元素值从 1 开始映射）。​

（二）实例解析​

同样以 “添加、删除元素，查询小于 x 的元素个数” 为例，假设元素值经过映射后在 1 到 10 的范围内。​

树状数组初始化为全 0。添加元素 3（映射后索引为 3），对树状数组索引 3 进行加 1 操作。添加元素 5（映射后索引为 5），对索引 5 进行加 1 操作。此时查询小于 6 的元素个数，即查询索引 1 到 5 的前缀和，结果为 2。​

删除元素 3，对索引 3 进行减 1 操作，再查询小于 6 的元素个数，结果为 1。​

（三）优缺点及适用场景​

优点：更新和查询操作的时间复杂度都为 O (logn)，兼顾了两者的效率，对于元素范围较大但查询和更新操作都比较频繁的情况非常适用。​

缺点：实现相对复杂一些，需要理解树状数组的结构和相关操作的原理。而且元素需要进行合适的映射，确保其能够对应到树状数组的索引上。​

适用场景：适用于元素范围较大，且查询和更新操作都比较频繁的情况。​

五、总结归纳​

本文介绍了 LeetCode 中动态计数更新问题的三种解法：哈希表法、前缀和法和树状数组法。​

哈希表法实现简单，更新效率高，但查询效率较低，适合更新频繁、查询少或元素少的场景；前缀和法查询效率极高，但对元素范围有要求，适合元素范围小且查询频繁的情况；树状数组法更新和查询效率都不错，不过实现较复杂，适合元素范围大且更新查询都频繁的场景。​

在解决实际问题时，我们需要根据问题中元素的特点、更新和查询操作的频率等因素，选择合适的解法，以达到高效解决问题的目的。通过对这三种解法的学习和实践，新手可以更好地应对 LeetCode 中的动态计数更新问题，提升自己的算法解题能力。