基于字符的特性，0-256，他的哈希的方法主要是用数组的方式体现的0-256，或0-26，创建这样的数组来表述字符串的某种特性，这是字符串查找题目的一个特质
具体题目：
50题 找出字符串中找出第一个只出现一次的字符，比如输入“abacceff",则输出'b'
要想知道某个字符是不是只出现了一次，必须遍历字符串的每个字符。因此可以先遍历一次，统计每个字符出现次数。再遍历一次，遇到某个字符出现字符为1就立即返回。统计每个字符出现次数，可以用哈希表，不过如果输入中都是ASCII码，那么使用0-255表示即可。这样使用一个int[] count = new int[256]就能代替哈希表了，以count[someChar] = times这种方式表示某个字符出现的次数。比如‘a’的ASCII码是97，那么count[97]就表示了字符'a'的出现次数，以此类推。
java
package Chap5;
public class FirstAppearOnceChar {
/**
* 返回第一个不重复字符
*/
public char firstNotRepeatingChar(String str) {
if (str == null || str.length() == 0) return '\0';
int[] count = new int[256];
for (int i = 0; i < str.length(); i++) {
count[str.charAt(i)]++;
}
for (int i = 0; i < str.length(); i++) {
if (count[str.charAt(i)] == 1) return str.charAt(i);
}
return '\0';
}
/**
* 返回第一个不重复字符在字符串中的索引
*/
public int firstAppearOnceChar(String str) {
if (str == null || str.length() == 0) return -1;
int[] count = new int[256];
for (int i = 0; i < str.length(); i++) {
count[str.charAt(i)]++;
}
for (int i = 0; i < str.length(); i++) {
if (count[str.charAt(i)] == 1) return i;
}
return -1;
}
}
上面两个方法，一个是返回第一个只出现一次的字符，一个返回第一个只出现一个的字符的索引，思路都一样。根据count[someChar]获取某个字符的出现次数时间复杂度为O(1),对于长度为n的字符串，总的复杂度为O(n).
48-字符流中第一个只出现一次的字符。
这次字符串是动态变化的了，比如现在只从字符流中读取了两个字符为"go"那么字符流中第一个只出现一次的字符是'g'，等到从字符流中读取了前6个字符"google"时，第一个只出现一次的字符变成了'l'.
使用一个insert函数模拟从字符流中读到一个字符。这次统计表`int[] occur = new int[256]`记录的是字符出现的索引.
- 如果某个字符出现过，那么`occur[someChar] >= 0`;
- 对于没有出现过的字符，令`occur[someChar] = -1`;
- 如果某个字符第二次出现，令`occur[someChar] = -2`。
要获得当前字符串中第一个只出现一次的，只需从所有`occur[someChar] >= 0`中结果中找出出现索引最小的那个字符即可。
如果第一次出现，将bt[ch]设置为index(字符出现的顺序)，是大于0的，
如果重复出现了，就将bt[ch]设置为-1.
FirstAppearingOnce()的原理是，每次遍历数组，得到值大于0且index最小的那个位置i，再把i强转为char类型，就是要返回的字符
```java
public class Solution {
int[] count = new int[256];
int index=1;
//Insert one char from stringstream
public void Insert(char ch)
{
if(count[ch] == 0){
count[ch]=index++;
}else
count[ch]= -1;
}
//return the first appearence once char in current stringstream
public char FirstAppearingOnce()
{
int temp=Integer.MAX_VALUE;
char ch='#';
for(int i=0;i<256;i++){
if(count[i]>0 && count[i]<temp){
temp=count[i];
ch=(char)i;
}
}
return ch;
}
}
剑指offer面试题49--最长不含重复字符串的子字符串
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。假设字符串中只包含'a'~'z'之间的字符，例如在字符串"arabcacfr"中，最长的不含重复字符的子字符串是"acfr"，长度为4
动态规划，定义表示以第i个字符为结尾的不含重复字符的子字符串长度。
如果第i个字符之前没有出现过，则，比如‘abc',
是必然的，然后字符’b‘之前没有出现过，则
, 字符’c'之前没有出现过，那么
,每次计算都会用到上一次计算的结果。
如果第i个字符之前出现过呢？找到该字符上次出现的位置preIndex，当前位置i - preIndex就得到这两个重复字符之间的距离，设为d。此时有两种情况
如果
d <= f(i-1),说明当前重复字符必然在f(i-1)所对应的字符串中，比如’bdcefgc‘，当前字符c前面出现过了，preIndex为2，此时d = 6 -2 = 4,小于f(i -1) = 7 (bdcefg)我们只好丢弃前一次出现的字符c及其前面的所有字符，得到当前最长不含重复字符的子字符串为’efgc‘，即f(i) = 4, 多举几个例子就知道，应该让f(i) = d；如果
d > f(i-1), 这说明当前重复字符必然在f(i-1)所对应的字符串之前，比如erabcdabr当前字符r和索引1处的r重复，preIndex =1, i = 8,d = 7。而f(i -1) = 4 (cdab),此时直接加1即可，即f(i) = f(i-1) +1
package Chap5;
public class LongestSubstring {
public int findLongestSubstring(String str) {
int curLen = 0;
int maxLen = 0;
// 0~25表示a~z，position[0] = index,表明a上次出现在index处
int[] position = new int[26];
for (int i = 0; i < 26; i++) {
position[i] = -1;
}
for (int i = 0; i < str.length(); i++) {
int preIndex = position[str.charAt(i) - 'a'];
// 字符第一次出现，或者d > f(i -1)
if (preIndex == -1 || i - preIndex > curLen) curLen++;
// d <= f(i -1)
else {
if (curLen > maxLen) maxLen = curLen;
curLen = i - preIndex;
}
// 记录当前字符出现的位置
position[str.charAt(i) - 'a'] = i;
}
if (curLen > maxLen) maxLen = curLen;
return maxLen;
}
}
