算法之美(4):无重复字符的最长子串

int lengthOfLongestSubstring(char* s)

{
    //定义数据结构
    int hashMap[128];  //key 字符 value 字符对应的下标 定义不是 char hashMap[128];
    //为什么是128 ASCII 字符集标准中定义了 128 个字符，对应编号 0 ~ 127
    memset(hashMap,-1,sizeof(hashMap));
    //unsigned char 是唯一可以无损表示、访问任意类型对象的内存的类型。
    //According to the C and C++ standards
    //The object representation of an object is the sequence of unsigned char stored in memory
    //https://en.cppreference.com/w/cpp/string/byte/memset

    char* startPtr = s; // 窗口起点指针

    int startIndex = 0; // 记录窗口起点的索引

    char* endPtr = s;   // 窗口终点指针,因为指针结构 不清楚当前字符串的长度。

    int maxLen = 0;// 保存最大长度
    char tempChar;

    //在C语言设计之初，计算机的内存资源非常有限。

    // 为了最大限度地节省内存，C语言选择了使用一个单一的字节（'\0'）来标记字符串结束，

    // 而不是像一些其他语言那样记录字符串的长度。如果采用记录长度的方式，

    // 可能需要额外的几个字节来存储长度信息

    //数组像制作一样使用。这里为体现c语言特性 故意没有

    while(*endPtr != '\0')

    {
        tempChar= *endPtr; //字符--位置

        //重复,原来重复字符串不符合要求

        if(hashMap[tempChar] != -1 && hashMap[tempChar] >= (startPtr -s )){

            // char* s = "hello";

            // char* start = s + 2; // 指向字符 'l'，即索引为2的位置

            // int offset = start - s; // offset == 2

             startPtr = s + hashMap[tempChar] + 1; // 指针跳转
        }

        // 更新字符最新出现位置

        hashMap[tempChar] = (int)(endPtr - s); //指针可以之间相减

  

        int curLen = (int)(endPtr - startPtr) + 1;

        if (curLen > maxLen) {

            maxLen = curLen;

        }

        endPtr++;
    }
    return maxLen;

}

class Solution {

public:

 int lengthOfLongestSubstring(string s) {
 
  int ret =0;
  
  int begin =0; //开始位置
  
  int end =0;
  
  vector<int> hash(128,-1); //hash[s[i]]=i;
  
  for(end =0;end<s.size();end++)
  
  {
   char temp =s[end];
   
   if(hash[temp]!=-1 && hash[temp] >=begin)
   {
    begin=hash[temp]+1;
   }
   
   ret =max(ret,end-begin+1);
   
   hash[temp]=end;
  
  }
  return ret;
 }
};

func lengthOfLongestSubstring(s string) int {
    //定义数据结构
    const asciiSize = 128
    hashMap := [asciiSize]int{}
    for i := range hashMap {
        hashMap[i] = -1
    }
    start, maxLen := 0, 0
    // 实现算法
    for i, ch := range s {
        if hashMap[ch] >= start {
            start = hashMap[ch] + 1
        }
        hashMap[ch] = i
        maxLen = max(maxLen, i - start + 1)
    }
    return maxLen
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

use std::collections::HashMap;

impl Solution {
    pub fn length_of_longest_substring(s: String) -> i32 {
        let mut map = HashMap::new(); // 存字符 -> 最新索引
        let (mut start, mut max_len) = (0usize, 0usize);

        for (i, c) in s.chars().enumerate() {
        //Rust 的模式匹配写法，用来**判断 
        //HashMap 中是否有键 `c` 的值**，并把值绑定给 `prev_index`。
            if let Some(&prev_index) = map.get(&c) {
                if prev_index >= start {
                    start = prev_index + 1;
                }
            }
            map.insert(c, i);
            max_len = max_len.max(i - start + 1);
            //`.max()` 方法是 Rust 标准库 `Ord` trait 自带的
        }

        max_len as i32 //返回 `i32`
    }
}

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        char_index = {} //用大括号 `{}` 创建空字典
        start = 0
        max_len = 0
         //`enumerate` 是 Python 内置函数，
         //常用来在遍历序列（如列表、字符串）时，同时获得元素的索引和值
        for i, c in enumerate(s):
            //有重复元素
            if c in char_index and char_index[c] >= start:
                start = char_index[c] + 1
            char_index[c] = i
            max_len = max(max_len, i - start + 1)

        return max_len