HOT100 hash

3. Longest substring without repeating characters
   Given a string s , Please find out that there are no duplicate characters in it Longest substrings The length of .

Example 1:

Input : s = “abcabcbb”
Output : 3
explain : Because the longest substring without repeating characters is “abc”, So its length is 3.

Use sliding windows , The specific algorithm is ：
for In circulation i Is the right value of the window , Set an lvalue to 0, If the current window does not contain duplicate elements , Then the right boundary slides to the right , If you include , Then the left boundary is the position of the repeating element plus 1.
Notice when selecting the left boundary , The current character is not contained in the current longest valid sub segment , Such as ：abba, Let's add a,b Into the map, here left=0, Let's add b, Find out map Contained in the b, and b Included in the longest valid sub segment , Namely 1） The situation of , We update left=map.get(b)+1=2, At this time, the sub segment is updated to b, and map It still contains a,map.get(a)=0; And then , We traverse to a, Find out a Included in map in , And map.get(a)=0, If we look like 1） Handle it the same way , You will find left=map.get(a)+1=1, actually ,left here It should remain the same ,left Always be 2, Sub segment becomes ba That's right .

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

17. Letter combination of telephone number
    Given a number only 2-9 String , Returns all the letter combinations it can represent . You can press In any order return .

The mapping of numbers to letters is given as follows （ Same as phone key ）. Be careful 1 Does not correspond to any letter .
Example 1：

Input ：digits = “23”
Output ：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]

Recursive backtracking
Be careful add No need to delete after completion letters The last letter

class Solution {
    
    public List<String> letterCombinations(String digits) {
    
        
        List<String> combinations = new ArrayList<String>();
        if (digits.length() == 0) {
    
            return combinations;
        }
        Map<Character, String> phoneMap = new HashMap<Character, String>() {
    {
    
            put('2', "abc");
            put('3', "def");
            put('4', "ghi");
            put('5', "jkl");
            put('6', "mno");
            put('7', "pqrs");
            put('8', "tuv");
            put('9', "wxyz");
        }};
        digui(combinations,phoneMap,digits,0,new StringBuffer());
        return combinations;

    }
    public void digui(List<String> combinations,Map<Character, String> phoneMap,String digits, int index, StringBuffer letters){
    
        if(index == digits.length()){
    
            combinations.add(letters.toString());
            
            return;
        }
        String content = phoneMap.get(digits.charAt(index));
        for(int i = 0; i < content.length(); i++){
    
            char c = content.charAt(i);
            letters.append(c);
            digui(combinations,phoneMap,digits,index+1,letters);
            letters.deleteCharAt(index);

        }
    }

}