HashMap?

Java HashMap | 菜鸟教程

HashMap 是一个散列表，它存储的内容是键值对(key-value)映射。

HashMap 实现了 Map 接口，根据键的 HashCode 值存储数据，具有很快的访问速度，最多允许一条记录的键为 null，不支持线程同步。

HashMap 是无序的，即不会记录插入的顺序。

HashMap 继承于AbstractMap，实现了 Map、Cloneable、java.io.Serializable 接口。

HashMap 的 key 与 value 类型可以相同也可以不同，可以是字符串（String）类型的 key 和 value，也可以是整型（Integer）的 key 和字符串（String）类型的 value。

HashMap 中的元素实际上是对象，一些常见的基本类型可以使用它的包装类。

基本类型对应的包装类表如下：

基本类型	引用类型
boolean	Boolean
byte	Byte
short	Short
int	Integer
long	Long
float	Float
double	Double
char	Character

HashMap 类位于 java.util 包中，使用前需要引入它，语法格式如下：

import java.util.HashMap; // 引入 HashMap 类

以下实例我们创建一个 HashMap 对象 Sites，整型（Integer）的 key 和字符串（String）类型的 value：

HashMap<Integer, String> Sites = new HashMap<Integer, String>();

//添加元素 添加键值对(key-value):
Sites.put(1, "Google");
Sites.put(2, "Runoob");
Sites.put(3, "Taobao");
Sites.put(4, "Zhihu");
//System.out.println(Sites);
//{four=Zhihu, one=Google, two=Runoob, three=Taobao}
        
//访问元素 获取 key 对应的 value:
Sites.get(3));
//System.out.println(Sites.get(3));
//Taobao

//删除元素 删除 key 对应的键值对(key-value):
Sites.remove(4);
//System.out.println(Sites);
//{1=Google, 2=Runoob, 3=Taobao}

//删除元素 删除所有键值对(key-value):
Sites.clear();
//System.out.println(Sites);
//{}

//计算大小 计算 HashMap 中的元素数量
Sites.size();
//System.out.println(Sites.size());
//4

containsKey()	//检查 hashMap 中是否存在指定的 key 对应的映射关系。
containsValue()	//检查 hashMap 中是否存在指定的 value 对应的映射关系。

3. 无重复字符的最长子串
滑动窗口

通常用来解决子串、子序列、子数组问题

什么是滑动窗口？

其实就是一个队列,比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！

如何移动？

我们只要把队列的左边的元素移出就行了，直到满足题目要求！

一直维持这样的队列，找出队列出现最长的长度时候，求出解！

时间复杂度： $O(n)$

1、首先，判断当前字符是否包含在map中，如果不包含，将该字符添加到map（字符，字符在数组下标）,此时没有出现重复的字符，左指针不需要变化。此时不重复子串的长度为：i-left+1，与原来的maxLen比较，取最大值；

2、如果当前字符 ch 包含在 map中，此时有2类情况：
? ?1）当前字符包含在当前有效的子段中，如：abca，当我们遍历到第二个a，当前有效最长子段是 abc，我们又遍历到a，那么此时更新 left 为 map.get(a)+1=1，当前有效子段更新为 bca；
? ?2）当前字符不包含在当前最长有效子段中，如：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才对。

为了处理以上2类情况，我们每次更新left，left=Math.max(left , map.get(ch)+1).
另外，更新left后，不管原来的 s.charAt(i) 是否在最长子段中，我们都要将 s.charAt(i) 的位置更新为当前的i，
因此此时新的 s.charAt(i) 已经进入到当前最长的子段中！

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length() == 0) 
            return 0;

        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int maxLen = 0; //无重复子串的 最长字串的 长度
        int left = 0; //滑动窗口左指针

        for(int i = 0; i < s.length(); i++){
            if(map.containsKey(s.charAt(i))){ //判断当前字符是否包含在map中
                left = Math.max(left,map.get(s.charAt(i)) + 1);
            }  //charAt()方法用于返回指定索引处的字符
               //索引范围为从 0 到 length() - 1  String类
            map.put(s.charAt(i),i);
            maxLen = Math.max(maxLen,i-left+1);
        }
        return max;
        
    }
}

作者：powcai
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/hua-dong-chuang-kou-by-powcai/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Java List接口

Java List<>的用法及其方法_Pompey_hpy的博客-CSDN博客_java list<>

Java 集合框架 | 菜鸟教程

List包括List接口以及List接口的所有实现类。因为List接口实现了Collection接口，所以List接口拥有Collection接口提供的所有常用方法，又因为List是列表类型，所以List接口还提供了一些适合于自身的常用方法。

在这里插入图片描述

List接口提供的适合于自身的常用方法均与索引有关，这是因为List集合为列表类型，以线性方式存储对象，可以通过对象的索引操作对象。
List接口的常用实现类有ArrayList和LinkedList，在使用List集合时，通常情况下声明为List类型，实例化时根据实际情况的需要，实例化为ArrayList或LinkedList，例如：

List<String> l = new ArrayList<String>();// 利用ArrayList类实例化List集合
List<String> l2 = new LinkedList<String>();// 利用LinkedList类实例化List集合

Java ArrayList | 菜鸟教程

ArrayList 类是一个可以动态修改的数组，与普通数组的区别就是它是没有固定大小的限制，我们可以添加或删除元素。?

ArrayList 继承了 AbstractList ，并实现了 List 接口。

ArrayList 类位于 java.util 包中，使用前需要引入它，语法格式如下：

import java.util.ArrayList; // 引入 ArrayList 类

ArrayList<E> objectName =new ArrayList<>();　 // 初始化

?30. 串联所有单词的子串

1. 总共用到两个哈希表，allWords 用于记录 words 中单词出现的次数，hasWords 用于记录子串中（也就是滑动窗口中）单词出现的次数
2. wordNum 为单词的个数，wordLen 为单词长度
3. 遍历字符串，移动长度为 wordNum * wordLen 的滑动窗口，再在当前滑动窗口中依次比较wordLen长度的单词
4. 当这个窗口内一旦出现不存在 allWords 中的单词，或者这个单词在子串中出现的次数已经等于 allWords 中的次数(也就是再加入这个子串次数就要超出了)，这个滑动窗口就不符合要求，直接 break 进入下一个滑动窗口的匹配
5. 一旦完全匹配上了，把滑动窗口的起始索引加入结果 res 中

时间复杂度： $O(n*m)$ ， $n$ 为字符串长度， $m$ 为单词个数
空间复杂度： $O(m)$

作者：edelweisskoko
链接：https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/solution/30-chuan-lian-suo-you-dan-ci-de-zi-chuan-bvy9/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        //allWords存储words中的所有单词
        HashMap<String, Integer> allWords = new HashMap<String, Integer>();
        for(String word : words){//for (Object o : list) { System.out.println(o);}
                            //优点：简洁结合泛型使用更简洁
                            //缺点：jdk1.4向下不兼容
                            //for (int i = 0; i < list.size(); i++) 
                            //{ System.out.println(list.get(i));}
            //getOrDefault获取 word 所对应的value; 没有 word, 返回默认值 0 
            allWords.put(word, allWords.getOrDefault(word,0) + 1); //将 word 存储进 map
        }

        List<Integer> res = new ArrayList<Integer>();
        int wordNum = words.length; //words里面有几个单词
        int wordLen = words[0].length(); //每个单词的长度, 题目隐藏条件:每个单词长度相等
        if(wordNum == 0)
            return res;

        for (int i = 0; i < s.length() - wordNum * wordLen + 1; i++){
            //hasWord存储s的子串中的单词
            HashMap<String, Integer> hasWords = new HashMap<String, Integer>();
            int index = i;

            while(index < i + wordNum * wordLen){
                String curWord = s.substring(index, index + wordLen);
                //判断word是否在map中
                if(!allWords.containsKey(curWord) || hasWords.get(curWord) == allWords.get(curWord)){//get()	获取指定 key 对应对 value
                    break;   
                }
                hasWords.put(curWord, hasWords.getOrDefault(curWord,0) + 1);
                index += wordLen;
            }
            if (index == i + wordNum * wordLen)
                res.add(i); 
        }

    return res;    
    }   
}

76. 最小覆盖子串

我写了一首诗，把所有滑动窗口问题变成了默写题

//模板
/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {
    Map<Character, Integer> need = new HashMap<>();
    Map<Character, Integer> window = new HashMap<>();

    for (char c : t.toCharArray()) 
        need.put(c, need.getOrDefault(c,0) + 1);
     int left = 0, right = 0; //双指针 左开右闭区间[left, right)为一个窗口
     int valid = 0; // 窗口中满足need条件的字符个数

     while (right < s.size()) {
         // c 是将移入窗口的字符
         char c = s.charAt(right);
         // 右移窗口
         right ++;
         // 进行窗口内数据的一系列更新 
         // 目的在于寻找一个【可行解】
         ...

         /*** debug 输出的位置 ***/
         System.out.println("window: ["+left+","+ right+")");
         /********************/
    
         // 判断左侧窗口是否要收缩
         while (window needs shrink) {
             // d 是将移出窗口的字符
             char d = s[left];
             // 左移窗口
             left ++;
             // 进行窗口内数据的一系列更新
             ...
            // 目的在于优化【可行解】,最终找到【最优解】
         }
     }
}

class Solution {
    public String minWindow(String s, String t) {
        //need中存储的时需要的字符以及需要的字符所对应的数量
        HashMap<Character, Integer> need = new HashMap<Character, Integer>();
        for(char c : t.toCharArray()){ //toCharArray() 方法将字符串转换为字符数组
            need.put(c, need.getOrDefault(c,0)+1);
        }

        HashMap<Character, Integer> window = new HashMap<Character, Integer>();
        int left = 0, right = 0; //双指针
        int count = 0; //记录当前窗口中符合need要求的字符的数量，当count==need.size()时即可shrink窗口
        int start = 0; //符合最优解的substring的起始索引
        int len = Integer.MAX_VALUE; //记录最终窗口的长度，以len作比较，淘汰选出最小的substring的len
        while(right < s.length()){
            //更新窗口
            char c = s.charAt(right);
            right ++; //窗口扩大
            if(need.containsKey(c)){
                window.put(c, window.getOrDefault(c,0)+1);
                if(need.get(c).equals(window.get(c))){
                    count++;
                }
            }
            //判断左侧窗口是否要收缩
            while(count == need.size()){
                //更新最小覆盖子串
                if(right - left < len){
                    len = right - left;
                    start = left;
                }

                char d = s.charAt(left); //d是将移除窗口的字符
                left ++; //窗口缩小，左移窗口
                //进行窗口数据的一系列更新
                if(need.containsKey(d)){   
                    if(need.get(d).equals(window.get(d))){
                        count--;
                    }
                    window.put(d, window.getOrDefault(d,0)-1);
                } 
            }
            

        }
        //返回最小覆盖子串
        return len == Integer.MAX_VALUE ? "":s.substring(start, start+len);   //int y = x1 == null ? 0 : x; 
                                                                            // if(x1==null){
                                                                            // 	y = 0;
                                                                            // }else{
                                                                            // 	y = x;
                                                                            // }

    }
}