一起学Rust-实战leetcode（二）

• 2019 年 10 月 4 日
• 筆記

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。 示例 2: 输入: "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。 示例 3: 输入: "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters

这是来源于leetcode的一道题 “无重复字符的最长子串”，我们使用Rust来实现。

本次实战的目的：

复习字符串的遍历， match 匹配， Option<T> 的使用和 HashMap 的使用。

简单分析：

首先还是进行简单的分析，题目要求获取的是子串，也就是必须是连续的，而且不能重复，最后一个要求是最长的。

所以考虑到连续且不重复，可以使用遍历所有字符并且使用HashMap来处理重复字符，通过记录每个字符直到遇到重复或到字符串结束的长度，进行比较获取最大的不重复字串长度。

最直接的思考方式就是，通过从字符串起始遍历，依次使用HashMap记录每一个字符和它的位置，使用字符作为key，字符位置作为值，遇到重复字符则可以更新位置。

遇到重复值情况：

需要计算当前位置与子串开始位置的差，也就是当前不重复子串的长度。

没有重复值情况：

直接对子串的长度进行步长为1的递增即可，直到遇到重复值或遍历结束。

比较最大长度：

每一轮遍历都会产生一次子串长度的递增或者是子串长度差值的计算结果，所以只保留这些结果中最大的就是最终的答案“无重复字符的最长子串”。

上面未解决的问题：如何计算子串的开始位置呢？

默认初始化时，子串的开始位置就是字符串的下标起始，值为0，当遇到重复字符时，便可以获取到当前字符的前一个重复的位置（例如 fgabcac 中，当遍历到第6个字符时，可以获取到a的前一个位置就是下标2），使用这个位置与原子串开始位置相比，取较大的一个位置作为开始位置，否则继续向下遍历时子串中就会包含两个相同的字符，不符合要求。

实现：

fn length_of_longest_substring(s:String) -> i32 {      // 初始化哈希map，key为字符类型（适用unicode字符处理）      let mut rec = HashMap::<char, usize>::new();      // 初始化最大长度，子串起始位置，子串临时长度      let (mut max_len, mut start, mut tmp_len) = (0_i32, 0_i32, 0_i32);        // 遍历字符串      for (k, c) in s.chars().enumerate() {          match rec.get(&c) {              Some(v) => {                  //获取下一个无重复子串开始位置                  start = start.max(*v as i32);                  //重新计算新子串的长度                  tmp_len = k as i32 - start;              },              None => {                  // 无重复时对子串长度递增                  tmp_len += 1;              }          }          //取各个子串长度中最大的          max_len = max_len.max(tmp_len);            //记录字符和位置          rec.insert(c, k);      }      //返回最大长度      max_len  }