统计字符串中唯一字符数量的优化方法，主要目标是降低时间复杂度。以下是几种常见的优化思路和实现方式：✅ 1. 使用哈希表（Hash Map）或集合（Set）时间复

本文旨在探讨如何高效统计字符串中唯一字符的个数。虽然理论上的时间复杂度下限为 O(n)，但通过合理选择数据结构，可以优化内存使用并提升实际性能。本文将分析基于 HashSet 的常见方法，并介绍使用固定大小数组的优化策略，最后讨论其适用场景和局限性。

使用 HashSet 统计唯一字符

一种常见的解决方案是使用 HashSet 来存储字符串中的每个字符。由于 HashSet 具有自动去重的特性，因此最终 HashSet 中元素的个数即为字符串中唯一字符的个数。

以下是 Java 代码示例：

import java.util.HashSet;

public class UniqueCharacters {

    public static int countUniqueCharacters(String s) {
        HashSet uniqueChars = new HashSet<>();
        for (int i = 0; i < s.length(); i++) {
            uniqueChars.add(s.charAt(i));
        }
        return uniqueChars.size();
    }

    public static void main(String[] args) {
        String str = "abcaabbd";
        int uniqueCount = countUniqueCharacters(str);
        System.out.println("字符串 \"" + str + "\" 中唯一字符的个数为: " + uniqueCount); // 输出: 4
    }
}

这段代码的时间复杂度为 O(n)，其中 n 是字符串的长度。这是因为我们需要遍历字符串中的每个字符，并且 HashSet 的 add() 操作的平均时间复杂度为 O(1)。空间复杂度取决于字符串中唯一字符的数量，最坏情况下为 O(n)，即字符串中所有字符都是唯一的。

使用固定大小数组优化

虽然使用 HashSet 的方法在时间复杂度上已经达到了最优的 O(n)，但在某些特定情况下，我们可以通过使用固定大小的数组来优化内存使用。

适用场景：

• 字符串中的字符集是有限且已知的，例如 ASCII 字符集（256个字符）。

实现思路：

1. 创建一个长度为字符集大小的数组（例如，对于 ASCII 字符集，数组长度为 256）。
2. 遍历字符串，将每个字符对应的数组元素的值加 1。字符的 ASCII 码值可以用作数组的索引。
3. 遍历数组，统计非零元素的个数，即为字符串中唯一字符的个数。

以下是 Java 代码示例：

public class UniqueCharactersOptimized {

    public static int countUniqueCharactersOptimized(String s) {
        int[] charCounts = new int[256]; // 假设使用 ASCII 字符集
        for (int i = 0; i < s.length(); i++) {
            charCounts[s.charAt(i)]++;
        }

        int uniqueCount = 0;
        for (int count : charCounts) {
            if (count > 0) {
                uniqueCount++;
            }
        }
        return uniqueCount;
    }

    public static void main(String[] args) {
        String str = "abcaabbd";
        int uniqueCount = countUniqueCharactersOptimized(str);
        System.out.println("字符串 \"" + str + "\" 中唯一字符的个数为: " + uniqueCount); // 输出: 4
    }
}

这段代码的时间复杂度仍然是 O(n)，其中 n 是字符串的长度。但是，空间复杂度降低到了 O(1)，因为数组的大小是固定的，与字符串的长度无关。

注意事项：

• 这种方法只适用于字符集有限且已知的情况。如果字符集很大或者未知，则不适用。
• 在使用这种方法时，需要确保字符串中的字符都在字符集范围内。否则，可能会导致数组越界错误。

总结

统计字符串中唯一字符的个数是一个常见的编程问题。使用 HashSet 是一种通用的解决方案，具有良好的时间和空间复杂度。在字符集有限且已知的情况下，可以使用固定大小的数组来优化内存使用。选择哪种方法取决于具体的应用场景和对时间和空间复杂度的要求。在实际应用中，需要根据具体情况进行权衡，选择最合适的解决方案。