leetcode 3号题

Question

题目

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

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

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

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值存的是什么

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

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

加油！：）