leetcode 3号题

来源：15-1 更广阔的数据结构的世界，大家加油！

一个很坏的好人

2018-08-20

题目

我设置了两个游标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;
	}
}

写回答

2回答

一个很坏的好人

提问者

2018-08-20

懂了，之前不懂官方解答里面的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

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

2018-08-20

共1条回复