最长不重复子串

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

Example 1:

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

Example 2:

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

Example 3:

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

普通解法：遍历，循环，begin为字符串开头起始位置，[begin,i)之间的字符串是不重复的子串，内层循环判断i位置的字符是否与这个区间上的某个字符相等

class Solution {

    public int lengthOfLongestSubstring(String s) {

        int begin=0;

        int len=0;

        if(s.length()>0)

            len=1;

        for(int i=0;i<s.length(); i++)

        {

            for(int j=begin;j<i;j++)

            {

                if(s.charAt(i)==s.charAt(j))

                {

                    if(i-begin>len)

                        len=i-begin;

                    begin=j+1;

                    break;

                }

                else if(j==i-1)

                {

                    if(i-begin+1>len)

                        len=i-begin+1;

                }

            }

        }

        return len;

    }

}

哈希表解法：利用hashmap的<key,value>结构存储字符，value即为字符的位置

   public int lengthOfLongestSubstring(String s) {
        if (s.length()==0) return 0;
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int max=0;
        for (int i=0, j=0; i<s.length(); ++i){
            if (map.containsKey(s.charAt(i))){
                j = Math.max(j,map.get(s.charAt(i))+1);
            }
            map.put(s.charAt(i),i);
            max = Math.max(max,i-j+1);
        }
        return max;
    }