class Solution { public: int lengthOfLongestSubstring(string s) { map<char,int> hash; int ans = 0; int n= s.size(); for(int i= 0, j=0;j<n;j++){ if(hash.find(s[j])!=hash.end()) i=max(hash.find(s[j])->second+1,i); //当发现重复字符时，i直接跳到重复字符的下一位，改进了方法2中一个字符一个字符滑动窗口的方法 ans=max(ans,j-i+1); hash[s[j]]=j; } return ans; } };

这是一个使用滑动窗口算法解决无重复字符的最长子串问题的C++代码，使用了哈希表存储字符出现的位置。算法的时间复杂度为O(n)，其中n为字符串的长度。代码中的map容器是C++ STL中的关联容器，用于存储键值对，本代码中用来存储字符出现的位置。在遍历字符串时，维护两个指针i和j，分别表示子串的起始和结束位置，同时使用哈希表判断字符是否重复出现。当发现重复字符时，i直接跳到重复字符的下一位，避免了一个字符一个字符滑动窗口的方法，提高了算法的效率。最后返回最长子串的长度。

相关问题

class Solution {public: int lengthOfLongestSubstring(string s) { if(s.size() == 0) return 0; 讲解该代码

这是一段求解最长无重复子串长度的代码，下面对其进行讲解：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.size() == 0) return 0;  // 如果字符串为空，返回0

首先判断给定的字符串s是否为空，如果为空，那么最长无重复子串的长度为0。

        int maxLen = 1;  // 最长无重复子串的长度最小为1
        int start = 0;   // 子串的起始位置
        int end = 0;     // 子串的结束位置
        int n = s.size(); // 字符串s的长度
        unordered_set<char> hash; // 用一个哈希表记录出现过的字符
        while(end < n){
            if(hash.find(s[end]) == hash.end()){ // 如果当前字符不在哈希表中，将其加入哈希表
                hash.insert(s[end]);
                end++;  // 将子串的结束位置向右移动
                maxLen = max(maxLen, end - start); // 更新最长无重复子串的长度
            }else{ // 如果当前字符在哈希表中，就将子串的起始位置向右移动，直到子串中不包含当前字符为止
                hash.erase(s[start]);
                start++;
            }
        }
        return maxLen; // 返回最长无重复子串的长度
    }
};

接下来，定义三个变量maxLen、start和end，分别表示当前最长无重复子串的长度、子串的起始位置和子串的结束位置。同时，定义一个哈希表hash，用于记录已经出现过的字符。

接着，用while循环遍历整个字符串s，如果当前字符不在哈希表中，就将其加入哈希表，并将子串的结束位置向右移动。如果当前字符在哈希表中，就将子串的起始位置向右移动，直到子串中不包含当前字符为止。在子串的每一个位置，都要更新一下最长无重复子串的长度maxLen。

最后，返回最长无重复子串的长度maxLen。

用C语言改一下#include<iostream> #include<cstring> #include<iomanip> using namespace std; struct student{ char name[20]; int num; //学号 int number; //票数 int Class; char major[30]; char grade[10]; char achievement[200]; }; class votesystem{ private: studentst; int count; //当前元素个数 int size; //哈希表长 public: void InitHashTable(int n); //初始化哈希表 int Hash(charname); //计算哈希地址 void collision(int &s); //冲突，计算下一个地址 int search(char name,int &s); //查找 void insert(charname); //插入 int vote(char*name); //投票 void display(); //显示哈希表 void showvote(int k); //按哈希表下标显示票数 void showrank(); //显示排行榜 };

使用C语言改写该代码如下：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_NAME_LEN 20
#define MAX_MAJOR_LEN 30
#define MAX_GRADE_LEN 10
#define MAX_ACHIEVEMENT_LEN 200
#define HASH_TABLE_SIZE 100

typedef struct student {
    char name[MAX_NAME_LEN];
    int num; //学号
    int number; //票数
    int Class;
    char major[MAX_MAJOR_LEN];
    char grade[MAX_GRADE_LEN];
    char achievement[MAX_ACHIEVEMENT_LEN];
} student;

typedef struct HashNode {
    student st;
    int flag; //标记该位置是否被占用
} HashNode;

typedef struct votesystem {
    HashNode table[HASH_TABLE_SIZE];
    int count; //当前元素个数
} votesystem;

void InitHashTable(votesystem *vs) {
    vs->count = 0;
    for (int i = 0; i < HASH_TABLE_SIZE; i++) {
        vs->table[i].flag = 0;
    }
}

int Hash(char *name) {
    int hash_val = 0;
    for (int i = 0; name[i] != '\0'; i++) {
        hash_val = (hash_val * 31 + name[i]) % HASH_TABLE_SIZE;
    }
    return hash_val;
}

void collision(int *s) {
    (*s)++;
    if (*s == HASH_TABLE_SIZE) {
        *s = 0;
    }
}

int search(votesystem *vs, char *name, int *s) {
    int hash_val = Hash(name);
    while (vs->table[hash_val].flag != 0 && strcmp(vs->table[hash_val].st.name, name) != 0) {
        collision(s);
        hash_val = Hash(name) + *s;
    }
    if (vs->table[hash_val].flag == 0) {
        return -1; //未找到该元素
    } else {
        return hash_val;
    }
}

void insert(votesystem *vs, student st) {
    if (vs->count == HASH_TABLE_SIZE) {
        printf("Hash table is full!\n");
    } else {
        int s = 0;
        int hash_val = Hash(st.name);
        while (vs->table[hash_val].flag == 1) {
            collision(&s);
            hash_val = Hash(st.name) + s;
        }
        vs->table[hash_val].st = st;
        vs->table[hash_val].flag = 1;
        vs->count++;
    }
}

int vote(votesystem *vs, char *name) {
    int s = 0;
    int hash_val = search(vs, name, &s);
    if (hash_val == -1) {
        printf("Student %s not found!\n", name);
        return -1;
    } else {
        vs->table[hash_val].st.number++;
        return vs->table[hash_val].st.number;
    }
}

void display(votesystem *vs) {
    for (int i = 0; i < HASH_TABLE_SIZE; i++) {
        if (vs->table[i].flag == 1) {
            printf("name: %s, num: %d, number: %d, Class: %d, major: %s, grade: %s, achievement: %s\n",
                   vs->table[i].st.name, vs->table[i].st.num, vs->table[i].st.number,
                   vs->table[i].st.Class, vs->table[i].st.major, vs->table[i].st.grade,
                   vs->table[i].st.achievement);
        }
    }
}

void showvote(votesystem *vs, int k) {
    if (k >= 0 && k < HASH_TABLE_SIZE && vs->table[k].flag == 1) {
        printf("name: %s, number: %d\n", vs->table[k].st.name, vs->table[k].st.number);
    } else {
        printf("Invalid index!\n");
    }
}

void showrank(votesystem *vs) {
    student *tmp_st = (student *) malloc(sizeof(student) * vs->count);
    int tmp_count = 0;
    for (int i = 0; i < HASH_TABLE_SIZE; i++) {
        if (vs->table[i].flag == 1) {
            tmp_st[tmp_count++] = vs->table[i].st;
        }
    }
    for (int i = 0; i < tmp_count - 1; i++) {
        for (int j = i + 1; j < tmp_count; j++) {
            if (tmp_st[i].number < tmp_st[j].number) {
                student tmp = tmp_st[i];
                tmp_st[i] = tmp_st[j];
                tmp_st[j] = tmp;
            }
        }
    }
    for (int i = 0; i < tmp_count; i++) {
        printf("%d. name: %s, number: %d\n", i + 1, tmp_st[i].name, tmp_st[i].number);
    }
    free(tmp_st);
}

int main() {
    votesystem vs;
    InitHashTable(&vs);
    student st1 = {"Tom", 1001, 0, 1, "Computer Science", "Grade 1", "Excellent"};
    student st2 = {"Jerry", 1002, 0, 1, "Computer Science", "Grade 1", "Good"};
    student st3 = {"Bob", 1003, 0, 1, "Computer Science", "Grade 1", "Average"};
    insert(&vs, st1);
    insert(&vs, st2);
    insert(&vs, st3);
    vote(&vs, "Tom");
    vote(&vs, "Jerry");
    vote(&vs, "Tom");
    vote(&vs, "Tom");
    display(&vs);
    showvote(&vs, Hash("Tom"));
    showrank(&vs);
    return 0;
}