leetcode03无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。

输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

1. 暴力法

遍历所有的子串，找出最长的不重复子串注意子串的边界问题，必须包含所有子串左边是从[0,n-1],右边是从[1,n];

public int lengthOfLongestSubstring(String s) {
		int max = 0;
		int n = s.length();
		// 判断的是左闭右开,[i,j)
		for (int i = 0; i != n; i++) {
			for (int j = i + 1; j <= n; j++) {
				if (allUnique(s, i, j)) {
					max = Math.max(max, j - i);
				} else
					break;

			}
		}
		return max;
	}

	public boolean allUnique(String s, int l, int r) {
		Set<Character> set = new HashSet<>();
		for (int i = l; i < r; i++) {
			// java集合里不能存放基本数据类型
			Character ch = s.charAt(i);
			if (set.contains(ch)) {
				return false;
			}
			set.add(ch);// char不能直接放在
		}
		return true;
	}

1.1 暴力法复杂度分析

遍历所有子数组时间复杂度为 $O (N^{2})$ ，判断没有子数组是否为无重复子串，最坏时间复杂度为O(N)，所以暴力法时间复杂度为 $O (N^{3})$ 。

2. 滑动窗口法

对于子数组的题要想到滑动窗口，这里的窗口可以用set集合，去重
滑动窗口，每次可以右扩的时候，计算一下当前的最大长度
不能右扩的时候，说明set中存在当前元素的值，窗口一直左移，移到此重复值去掉停止

public int lengthOfLongestSubstring_2(String s) {
		int res = 0;
		Set<Character> set = new HashSet<>();
		int l = 0, r = 0, n = s.length();

		while (l != n && r != n) {// 窗口的左右
			if (set.contains(s.charAt(r))) {// 窗口里有重复值
				set.remove(s.charAt(l++));// 把重复值及其之前的元素去掉，从新计算长度
			} else {
				set.add(s.charAt(r++));// 没有重复值，右扩
				res = Math.max(res, r - l);// [0,1,2]

			}
		}
		return res;
	}

2.1 滑动窗口法复杂度分析

复杂度分析时间复杂度：O(2n) = O(n)，在最糟糕的情况下，每个字符将被 i 和 j 访问两次。空间复杂度：O(min(m, n))，与之前的方法相同。滑动窗口法需要 O(k) 的空间，其中 k 表示 Set 的大小。而Set的大小取决于字符串 n 的大小以及字符集/字母 m 的大小

3.优化的滑动窗口法

使用HashMap当做窗口容器，我们可以直接计算出当前无重复子串的长度，而不需要通过窗口一步步左移，将重复元素移除
对于子数组的题要想到用hashMap记下索引和值，
遍历，把索引和值都存在HashMap，如果表中已存在当前值，直接跳到重复的值

public int lengthOfLongestSubstring_3(String s) {
		if (s.length() == 1)
			return 1;
		HashMap<Character, Integer> map = new HashMap<>();
		int res = 0, n = s.length();

		for (int i = 0, j = 0; i < n; i++) {
			if (map.containsKey(s.charAt(i))) {
				j = Math.max(map.get(s.charAt(i)), i);// 只能左移
			}
			res = Math.max(res, i - j + 1);// [j,i]的实际长度为i-j+1
			map.put(s.charAt(i), i + 1);// 存的是当前元素位置加1，也就是新的无重复子数组的左边界。
		}
		return res;
	}