#数组标记法在算法题中的应用
什么？！你还不知道数组在算法题中不仅起储存数据的作用，还可以起链接标记的作用？哈哈不要紧，原来我也是不知道的，我是看了我好哥们的做题思路才知道这个方法的。。。
----
我们先声明一个长度为5数组arr[5]，再为arr[5]赋值arr[]={"q","w","e","r",“t”}。这样我们访问arr[0]值为“q”，arr[1]值为w...你会发现通过数组arr[i]=某个字母，序号与字母形成了一种索引关系，即序号指向了数组中的某一个元素，这就好比Python中的字典，C++中的map，数组的序号可以看做是键（key），对应的元素就可以看做是值（value），这样我们就可以解决很多问题，比如让编译器和我们都头疼的数组（或字符串去重问题），PTA中有很多这样的例题，下面我们看一道。。。
---
1093 字符串A+B （20 分)
给定两个字符串 A 和 B，本题要求你输出 A+B，即两个字符串的并集。要求先输出 A，再输出 B，但重复的字符必须被剔除。
输入格式：
输入在两行中分别给出 A 和 B，均为长度不超过 10^6的、由可见 ASCII 字符 (即码值为32~126)和空格组成的、由回车标识结束的非空字符串。
输出格式：
在一行中输出题面要求的 A 和 B 的和。
输入样例：
This is a sample test
to show you_How it works
输出样例：
This ampletowyu_Hrk
---
字符串拼接可以说是基本操作，我们在这儿就不在赘述了（拼接后的的字符串我们声明为a吧），我们主要谈谈如何实现字符串去重，常规方法，也是最容易想到的方法就是，设立两层循环，复制a字符串（副本我们称之为b吧）外层循环遍历拼接后字符串的每个字母，内层循环用外层当前的字母i与副本b中的当前字符i以后的字符比较，如果在b中没有找到与当前字符相同的字符，我们就输出i；这样做的时间复杂度为O（n^2）.
我们大可以换个思路。。。字符和是否重合的状态其实是一个索引的关系，即每个字符对应了一种状态（有或无），这样我们就可以使用我们之间提到的数组来维持两者的关系。当然你会说数组的序号是一个数字，怎么能把字符当序号呢？答案是字符都对应这唯一的ASCII码啊，这就可以作为数组索引的目录。
(```)
#include<stdio.h>
#include<string.h>
int main()
{
char a1[100000];
char b1[100000];
int c[128] = { 0 };//初始化这个数组的的所有元素都为0
gets(a1);
gets(b1);
for (int i = 0; i <strlen(a1); i++)
{
if (c[a1[i]] == 0)
{
c[a1[i]] = 1;
printf("%c",a1[i]);
}
}
for (int i = 0; i < strlen(b1); i++)
{
if (c[b1[i]] == 0)
{
c[b1[i]] = 1;
/*每当出现一个新字符就讲b1[i]在c中对应的值改成1，当之后读取到c[b1[i]]==1时，程序就知道b1[i]在之前出现过了*/
printf("%c",b1[i]);
}
}
return 0;
}
(```)
这样我们就完成了对字符串的去重处理，时间复杂度O(n)，在OJ中更有优势。当然这只是数组标记法在本题中中的一个小小应用，至少在PTA中这个方法屡试不爽，希望大家都能够运用好此方法，为自己的算法刷题锦上添花。