题解 | #最长不含重复字符的子字符串#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param s string字符串
 * @return int整型
 */
#include <stdio.h>
#include <string.h>
int idn = 0;
struct {
    char exist;
    int idn;
} info[255];
//简单粗暴，直接定义ascii的结构体数组，方便做快速查找(不需要担心内存不够)
//结构体里面记录某个字符是否出现过，以及它的最新位置

//更新字符的位置
void add(unsigned char a, int i) {
    info[a] .exist = 1;
    info[a] .idn = i;
}

//先看这个字符是否存在，不存在直接返回fff(不可能有这么大），存在返回它的位置
int find(unsigned char a) {
    if (info[a].exist) {
        return info[a].idn;
    }
    return 0xfff;
}


int lengthOfLongestSubstring(char* s ) {
    // write code here
  //动态规划数组
    int sum[strlen(s)];
    int manx = 0;
    char* p = (char*)&info;
  //清0
    for (int i = 0; i < sizeof(info); i++) {
        p[i] = 0;
    }
//1：确认初识状态
    sum[0] = 1;
    add(s[0], 0);
    if (strlen(s) == 1) {
        return 1;
    }
  //dp状态方程
  //如果这个字符以前没有出现过  dp[i] = dp[i - 1]
  //如果字符出现过，需要讨论该字符出现的区间 
  
  	for (int i = 1; i < strlen(s); i++) {

        int k = find(s[i]);
        if (k != 0xfff) {
            sum[i] = (i - k) > sum[i - 1] ?  (sum[i - 1] + 1) :(i - k) ;
        } else {
            sum[i] = sum[i - 1] + 1;
        }
        add(s[i], i);
        if (sum[i] > manx) {
            manx = sum[i];
        }
    }
    return manx;
}