本文共 650 字，大约阅读时间需要 2 分钟。

Implement an algorithm to determine if a string has all unique characters. What if you can not use additional data structures?

1）使用附加结构：

这里需要假定的是字符都是ASCII码（1个字节表表示），大小256的为扩展ASCII码（0-255），128为标准ASCII（0-127）

bool hasAllUniqueChar(string str){	int a[256];	memset(a,0,sizeof(a));	for(int i=0;i
   
    1)			return false;	}	return true;}
   

评：答案中hash数组使用的不是int而是bool这样能减少空间的开销，这是我所没有想到的

2）不使用附加结构：

bool hasAllUniqueChar(string str){	for(int i=0;i

评：答案中提出当字符都是小写字母的时候可以使用位运算来操作，只需要一个整形变量，空间复杂度为O(1)，代码如下：

bool hasAllUniqueChar(string str){	int test=0;	for(int i=0;i

这儿使用了一个变量，如果任何附加变量也不使用的话，答案给出了当str结构可以破坏的时候对str进行排序，然后用两个指针i和j，不断向后移动，判断str[i]是否和str[j]相等。

转载地址：http://hfyab.baihongyu.com/