leetcode原题

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

示例 1:

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

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。

请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

解题思路

1.暴力肯定是可行的方法，但是需要耗费O（n²）的时间复杂度，pass

2.使用队列进行解题，将队列视为字符串中的滑动窗口，队列储存从i到j-1的无重复子字符串，当j在队列中不存在时，将j插入队列；

如j在队列中存在，将i依次往右移，直到队列中没有与j重复的元素，再将j插入队列。

同时每次记录队列最大值。复杂度为O（n），空间为O（k）。

3.思路与2相同，采用hashset进行储存数据，效率更高，复杂度相同。

4.使用hashmap进行（待思考，可查看leetcode官网

package leetcode;

import java.util.HashSet;
import java.util.Set;

public class LeetCode3 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String s = "abcbacbac";
		System.out.print(lengthOfLongestSubstring(s));
	}
	@SuppressWarnings("unlikely-arg-type")//eclipse中消除警告
	public static int lengthOfLongestSubstring(String s) {
		int a;
		int nums = 0;
		int leng = s.length();
		Set<Character> set = new HashSet<>();
		int i = 0, j = 0;
		while (i < leng && j < leng) {
			if (set.contains(s.charAt(j))!=true) {
				set.add(s.charAt(j++));
				nums = Math.max(nums, j - i);
			} else {
				set.remove(s.charAt(i++));
			}
			a=1+1;
		}
		return nums;
	}

}

hashmap