哈希 table 与字符串检查

Question

我正在编写一些代码来检查字符串中字符的重复。这是我在某处找到的一些答案。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int hash[256];
        for(int i=0; i<256; i++) hash[i] = -1;
        int start = 0, ans = 0;
        int i;
        for(i=0; i<s.size(); i++){
            if( -1 != hash[ s[i] ] ){
                if(ans < i-start) ans = i-start;//update max length
                for(int j=start; j<hash[ s[i] ]; j++) hash[j] = -1;
                if(hash[ s[i] ] + 1  > start )
                   start = hash[ s[i] ] +1;//update start if repeat happen
            }
            hash[ s[i]] = i;
        }
        if(ans < i-start) ans = i-start;
        return ans;
    }
};

有效，大部分地方都清楚了。我只是对几行感到困惑。

if( -1 != hash[ s[i] ] ){
                if(ans < i-start) ans = i-start;//update max length
                for(int j=start; j<hash[ s[i] ]; j++) hash[j] = -1;
                if(hash[ s[i] ] + 1  > start )
                   start = hash[ s[i] ] +1;
            }
            hash[ s[i]] = i;

这里有问题：

(1) 为什么要检查 hash[s[i]]!=-1？ s[i]是字符串中的字符，上面代码显示hash[i]，i是从0-256.

(2) 我很困惑

for(int j=start; j<hash[ s[i] ]; j++) hash[j] = -1;
                    if(hash[ s[i] ] + 1  > start )
                       start = hash[ s[i] ] +1;

请问它在做什么？

Answer 1

那不是哈希表。 hash 变量是一个 int 数组，由字符串中 char 的 ascii 代码索引，因此 hash[s[i]] 其中 s[i]=='A' 是 hash[63] .所以，它所做的是将字符的位置存储在由字符代码索引的数组中。

hash[s[i]]!=-1 检查是否出现字符

for(int j=start; j 从 start 到字符集 hash[position] 的当前位置为 -1。这一定是错误的或错误的，因为它混合了基于字符的具有 j.</p> 位置性质的哈希索引 <p> if(hash[ s[i] ] + 1 > start ) start = hash[ s[i] ] +1;如果当前字符的位置在start之后，则在当前字符之后设置start。

哈希 table 与字符串检查

Hash table with string check

c++

hashtable