内功修炼-算法02

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

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

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

/**
 * 思路一:
 *
 *      1.把字符串转换为字符数组
 *      2.把字符串逐个放入set集合(set),同时记录放入集合的数量(j)
 *      2.如果set集合长度和放入数量不符,记录该长度(l),清空set集合,把j设置为0,放入刚才放入的值,继续循环
 *      3.如果继续出现上述清空,和上面记录的长度进行对比,小于清空继续,大于更新记录长度
 *
 *      时间复杂度:T(N) 空间复杂度:O(1)
 *
 * 测试情况:不通过
 *
 * 总结分析:
 *
 *      1.没有考虑到空格字符串的情况
 */
public int lengthOfLongestSubstring1(String s) {
    char [] chars = s.toCharArray();
    Set set = new HashSet();
    int l=0;
    for (int i=0,j=0;i<chars.length;i++){
       set.add(chars[i]);
       j++;
       if (set.size()<j){
           l = Math.max(set.size(),l);
           set.clear();
           j = 1;
           set.add(chars[i]);
       }
    }
    return l;

}

/**
 * 思路二: 滑动窗口
 *
 *      1.定义一个map集合(map)，用于存储字符值和位置，key为字符，value为字符位置加1
 *      2.定义一个变量ans,用于记录时间窗最大长度
 *      3.定义时间窗起点start和时间窗结束点end
 *      4.然后把end向右滑动,最大长度为（end-start+1），如果map集合中存在该元素,说明遇到了重复的元素
 *          4.1.记录时间窗最大值ans
 *          4.2.移动时间窗start到重复元素第一个之后的位置
 *      5.继续滑动,直到j=字符串长度
 *
 */
public int lengthOfLongestSubstring2(String s) {
    int n = s.length(), ans = 0;
    Map<Character, Integer> map = new HashMap<>();
    for (int end = 0, start = 0; end < n; end++) {
        char alpha = s.charAt(end);
        if (map.containsKey(alpha)) {
            start = Math.max(map.get(alpha), start);
        }
        ans = Math.max(ans, end - start + 1);
        map.put(s.charAt(end), end + 1);
    }
    return ans;
}