题目链接｜字符个数统计

题意：编写一个函数，计算字符串中含有的不同字符的个数。字符在 ASCII 码范围内( 0~127 ，包括 0 和 127 )，换行表示结束符，不算在字符里。不在范围内的不作统计。多个相同的字符只计算一次 例如，对于字符串 abaca 而言，有 a、b、c 三种不同的字符，因此输出 3。

数据范围： $1\le n\le 5001\backslash leq\; n\backslash leq500$

输入描述： 输入一行没有空格的字符串。

输出描述： 输出 输入字符串 中范围在(0~127，包括0和127)字符的种数。

方法一：使用数组记录每种字符是否已经出现 (哈希表思想)

因为字符串的范围在0～127，最多只有128种字符。可以维护一个字符种类的变量，通过遍历字符串，并用数组记录当前字符是否已经出现。如果当前字符已经出现，种类数目不变，如果当前字符没有出现过，将记录的数组设成1，表示当前字符出现了，并同时更新种类数目。

时间复杂度：$O(N)O(N)$, 解释：需要遍历一遍输入的字符串。

空间复杂度：$O(M)O(M)$，解释：需要建一个数组记录每种字符是否出现。（$MM$为种类数目）

代码

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int ans=0;
int vis[128]={0};
string str;
int main() {
    cin>>str;
    int len=str.length();
    for(int i=0;i<len;i++){
        int asc=(int)str[i];
        if(vis[asc]==0) { //如果当前字符没出现过
            vis[asc]=1; //标记该字符的出现
            ans++; //增加字符种类统计数
        }
    }
    cout<<ans<<endl;
    return 0;
}

方法二：使用集合来统计（同样是哈希表的思想）

每次向集合中添加元素时，如果集合中已经有该元素，不会重复添加；如果集合中没有该元素，则会添加新元素。遍历字符串将每个字符添加到集合中，最后统计集合的大小，就是字符的种类数目。在C/C++中set的实现是红黑树。

时间复杂度：$O(Nlog(N))O(Nlog(N))$，解释：插入操作的复杂度是$O(log(N))O(log(N))$，操作$NN$次，所以复杂度是$O(NlogN)O(NlogN)$。

空间复杂度：$O(M)O(M)$，解释：使用树的结构维护$MM$个点的复杂度为$O(M)O(M)$。($MM$为种类数目)

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <set>
using namespace std;
string str;
set<char> ascs;
int main() {
    cin>>str;
    int len=str.length();
    for(int i=0;i<len;i++){
        ascs.insert(str[i]); //向集合中添加字符
    }
    cout<<ascs.size()<<endl; //输出集合的尺寸
    return 0;
}