leetcode 3号题

Question

题目

我设置了两个游标pq记录左右边界，

我这样写p每次只能位移一个单位，进行了一些重复的操作

怎样才能记录下来已经扫描过的不重复子串 提高效率？

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

class Solution {     public int lengthOfLongestSubstring(String s) {         int ret = 0;         int p = 0, q = 0;           while (q < s.length()) {             int length = 0;             HashSet<Character> set = new HashSet<>();             for (; q < s.length(); q++) {                 if (!set.contains(s.charAt(q))) {                     set.add(s.charAt(q));                     length++;                 } else {                     ret = length > ret ? length : ret;                     p++;                     q = p;                     break;                 }                 ret = length > ret ? length : ret;             }         }         return ret;     } }

Answer 1

提问者 一个很坏的好人 2018-08-20 13:32:51

懂了，之前不懂官方解答里面的map中value值存的是什么

原来存的是该字符对应的下一个位置

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

public class Solution {     public int lengthOfLongestSubstring(String s) {         int n = s.length(), ans = 0;         Map<Character, Integer> map = new HashMap<>(); // current index of character         // try to extend the range [i, j]         for (int j = 0, i = 0; j < n; j++) {             if (map.containsKey(s.charAt(j))) {                 i = Math.max(map.get(s.charAt(j)), i);             }             ans = Math.max(ans, j - i + 1);             map.put(s.charAt(j), j + 1);         }         return ans;     } }

• liuyubobobo #1

  赞！理解算法中变量的语意，是理解算法的关键，也是能够写出正确程序的关键：）继续加油！

Answer 2

liuyubobobo 2018-08-20 13:09:34

可以参考我的实现的第三种方式：https://github.com/liuyubobobo/Play-Leetcode/tree/master/0003-Longest-Substring-Without-Repeating-Characters

加油！：）