每天一题LeetCode- Longest Substring

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 解答时 有用hashMap 和hashSet 两种解法

hashSet

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

思路较为简单，如果里面已经有该值了，就移除前面的，直到没有重复

hashMap

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        Map<Character, Integer> map = new HashMap<>(); // current index of character
        // try to extend the range [i, j]
        for (int j = 0, i = 0; j < n; j++) {
            if (map.containsKey(s.charAt(j))) {
                i = Math.max(map.get(s.charAt(j)), i);
            }
            ans = Math.max(ans, j - i + 1);
            map.put(s.charAt(j), j + 1);
        }
        return ans;
    }
}

如果键相同 值会把后面的值给覆盖，思路就是如果Map 中已经有该值，就找到上一个重复的，并且与当前的i比较，取da