3.无重复字符的最长字串

这题使用的是滑动窗口法

我们把每个元素都存入了HashMap，其中key为字符，value为字符所在位置的下一个位置（字符下标+1），之所以这样做是因为如果字符串的子串中出现了重复元素，我们调用get方法可以直接得到新的子串的起点。终点比较简单，始终是我们当前遍历到的字符下标。

需要注意的是，我们在更新起点是，并不能直接让新的起点为get方法返回的位置，因为可能之前的起点已经在get方法返回的值之后了（也就是说，get方法返回的位置已经不在当前字串所占的位置中了，因为可能子串中的其他字符出现了重复，导致子串开头处于当前字符之前出现的位置之后）。

当然，更新最大长度的时候也需要注意，不能因为当前遍历到的字符没在HashMap中出现过就对最大长度直接加一，因为可能上一次遍历发生了起点的变化，导致子串改变，那么当前子串的长度应是end - start + 1而不是最大长度加一。

/**
 * 比较啰嗦但是好理解的写法
 * */
public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int len = s.length();
        int res = 0;
        int start = 0;
        int end = 0;
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < len; i++) {
            char alpha = s.charAt(i);
            if (!map.containsKey(alpha)) {
                map.put(alpha, i + 1);
                end = i;
                res =Math.max(end - start + 1, res); // 不能直接+1 因为上一次循环可能改变了start
            }
            else {
                start = Math.max(start, map.get(alpha));
                map.put(alpha, i + 1);
                end = i;
                res = Math.max(end -start + 1, res);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
//        String s = "abcabcbb";
//        String s = "bbb";
        String s = "pwwkew";
        int res = solution.lengthOfLongestSubstring(s);
        System.out.println(res);

    }
}

对上面的代码做了一优化

package No3_LongestSubstringWithoutRepeatingCharacters;

import java.util.HashMap;
import java.util.Map;
/**
 * 对上一种解法进行简化
 * */
public class Solution2 {
    public int lengthOfLongestSubstring(String s) {
        int len = s.length();
        int res = 0;
        Map<Character, Integer> map = new HashMap<>();
        for (int start = 0, end = 0; end < len; end ++) { // 把start和end写在这主要是为了内存释放
           char alpha = s.charAt(end);
           if (map.containsKey(alpha)) {
               start = Math.max(start, map.get(alpha));
           }
           map.put(alpha, end + 1);
           res = Math.max(res, end - start + 1);
        }
        return res;
    }

    public static void main(String[] args) {
        Solution2 solution = new Solution2();
        String s = "abcabcbb";
//        String s = "bbb";
//        String s = "pwwkew";
        int res = solution.lengthOfLongestSubstring(s);
        System.out.println(res);

    }
}

最后编辑于：2020.07.22 23:11:43