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

输入: “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^2) O(N2),判断没有子数组是否为无重复子串,最坏时间复杂度为O(N),所以暴力法时间复杂度为 O ( N 3 ) O(N^3) O(N3)

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;
	}