hot100 哈希

3. 无重复字符的最长子串
   给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

采用滑动窗口，具体算法为：
for循环里的i为窗口右值，设定一个左值为0，如果当前窗口中不包含重复元素，则右边界向右滑动，如果包含，则左边界为重复元素位置加1。
注意在选取左边界的时候，当前字符不包含在当前最长有效子段中，如：abba，我们先添加a,b进map，此时left=0，我们再添加b，发现map中包含b，而且b包含在最长有效子段中，就是1）的情况，我们更新 left=map.get(b)+1=2，此时子段更新为 b，而且map中仍然包含a，map.get(a)=0； 随后，我们遍历到a，发现a包含在map中，且map.get(a)=0，如果我们像1）一样处理，就会发现 left=map.get(a)+1=1，实际上，left此时 应该不变，left始终为2，子段变成 ba才对。

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. 电话号码的字母组合
    给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：

输入：digits = “23”
输出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]

递归回溯
注意add完之后不需要删除letters最后一个字母

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);

        }
    }

}