LeetCode第三题

题目

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. 
             Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

思路

• 双指针问题
• 利用java的set集合
• 从第一个字母开始遍历，由于set集合的不可重复性，所以遇到重复便更换前进指针
• 记录最大的长度
• 比如，“abccabcbb” 开始，i指针开始指针a,j指针也从a开始向后遍历，当遇到第二个c时候停在第二个c，开始移动i，知道i遍历到第三个c停止，i继续前几一个，无重复便继续前进。

代码

public class Solution {
    public int lengthOfLongestSubstring(String s) {
	     Set<Character> set = new HashSet<Character>();
        int length = s.length(),i=0,j=0,result=0;
        while(i<length&&j<length){
            if(set.contains(s.charAt(j))){
                set.remove(s.charAt(i++));
            }
            else{
                set.add(s.charAt(j++));
                result = Math.max(result,j-i);
            }
        }
        return result;
    }
}