Leetcode 567 242 以及Integer类中equals与“==“的区别

当然，我们前面提到，这道题应该有多种做法，下面尝试一下使用HashMap的做法：

HashMap的做法与使用数组的做法差别不大，无非是将数组存储的信息转化为HashMap。我们可以设置两个HashMap，一个为s1对应的need，一个是s2对应的window，在使用HashMap的时候，当window的字符个数与need的字符个数相同，则可以直接return true。由于使用HashMap的原因，我们可以每次都去遍历两个表的情况来确定两表的字符个数，而这里我想要以一种新的思路来解题，用一个变量cnt来记录HashMap的情况，每次当遍历s2中的元素c时，window中c元素个数等于need中c元素个数的时候进行cnt++，当cnt等于need.size()时，可以说明已经满足了need中的元素已全部在window中，从而return true。

代码如下：

（C++）

class Solution {
public:
    bool checkInclusion(string t, string s) {
    unordered_map need, window;
    for (char c : t) need[c]++;
    int left = 0, right = 0;
    int valid = 0;
    while (right < s.size()) {
        char c = s[right];
        right++;
        // 进行窗口内数据的一系列更新
        if (need.count(c)) {
            window[c]++;
            if (window[c] == need[c])
                valid++;
        }
        // 判断左侧窗口是否要收缩
        while (right - left >= t.size()) {
            // 在这里判断是否找到了合法的子串
            if (valid == need.size())
                return true;
            char d = s[left];
            left++;
            // 进行窗口内数据的一系列更新
            if (need.count(d)) {
                if (window[d] == need[d])
                    valid--;
                window[d]--;
            }
        }
    }
    // 未找到符合条件的子串
    return false;
    }
};

（Java）

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if (s2.length() < s1.length()) return false;
        Map need = new HashMap<>();
        Map window = new HashMap<>();
        for(int i=0;i=s1.length()){
                //当窗口大于所需要的长度，则进行缩小
                if(cnt==need.size())return true;//找到答案
                char ch = s2.charAt(left++);
                if(need.containsKey(ch)){
                    if(need.get(ch).equals(window.get(ch)))cnt--;
                    //当窗口中移出的c字符个数与need字符个数一致时，cnt-1
                    window.put(ch,window.getOrDefault(ch,0)-1);
                }
            }
        }
        return false;
    }
}

Java版本这里面有一个需要尤其注意的点，当在执行判断语句：

if(need.get(ch).equals(window.get(ch)))

我们要注意，这里不能使用

if(need.get(ch)==window.get(ch))

不然在执行第102个示例的时候会报错，因为第102个示例中，每个字母出现的次数非常多，我试着在idea中对s1进行了计数，结果如下：

 我很疑惑，于是上网查询资料，发现了问题，我们可以先看下面的例子：

 大家可以先想一下结果是什么，以下是结果：

 我感到很奇怪，于是查询了相关资料，总结了以下几点：

1.“==”是Java提供的比较运算符,用来比较两个变量指向的内存地址是否相同。当比较的类型是基础数据类型时，比较的是它们的值，而当比较的对象是对象类型时，则是比较它们的内存地址。而equals()是Object类提供的一个方法.Object中equals()方法的默认实现就是返回两个对象==的比较结果.这点我们可以从equals()方法的源码中看到。但是equals()方法是可以被重写的,所以我们在具体使用的时候需要重点关注equals()方法有没有被重写。

2.Object类的equals()方法：

Integer类的equals()方法：

intValue()方法：

可以看见 实际上Integer.equals()方法也就是两个类的值。

3. 为什么 c==d 输出结果为false呢？

    Integer a =12;
    Integer b =12;
    Integer c = 128;
    Integer d = 128;

 前面我们提到，“==”运算符比较的类型为对象时，比较的是地址，那么是不是c与d的地址不一样呢。可是如果这样想，a与b的地址应该是一样的才会返回true鸭，我继续从源码分析，我从Integer类中发现了这样一段话：

 我的英语水平极差，简单翻译一下，大概是说，当不用new一个新的Integer实例时，通常使用这个方法来返回一个示例，而不是下面的 构造函数：Integer(int)，这个方法通常用来返回范围为：-128~127的数值，当然也可以返回这个范围外的数值的实例。
也就是说，当我们进行 Integer a = 12; 的创建实例时，我们可以看到，是直接返回调用Integer(i)方法的Integer 实例的。
而当我们进行 Integer c = 128;的创建实例时，由于其值在这个范围外(-128~127)时，是会返回IntegerCache.cache[i + (-IntegerCache.low)];（这又是个啥？）查看源码如下：

private static class IntegerCache {
        static final int low = -128;
        static final int high;
        static final Integer cache[];

        static {
            // high value may be configured by property
            int h = 127;
            String integerCacheHighPropValue =
                sun.misc.VM.getSavedProperty("java.lang.Integer.IntegerCache.high");
            if (integerCacheHighPropValue != null) {
                try {
                    int i = parseInt(integerCacheHighPropValue);
                    i = Math.max(i, 127);
                    // Maximum array size is Integer.MAX_VALUE
                    h = Math.min(i, Integer.MAX_VALUE - (-low) -1);
                } catch( NumberFormatException nfe) {
                    // If the property cannot be parsed into an int, ignore it.
                }
            }
            high = h;

            cache = new Integer[(high - low) + 1];
            int j = low;
            for(int k = 0; k < cache.length; k++)
                cache[k] = new Integer(j++);

            // range [-128, 127] must be interned (JLS7 5.1.7)
            assert IntegerCache.high >= 127;
        }

        private IntegerCache() {}
    }

这实在是难以理解，我通过浏览大佬的说明，我终于明白原来当数值在(-128~127)范围内时，也就是说在-128到127之间的值会缓存到IntegerCache.cache中，所以在Integer x=在-128到127之间时，返回的是同一个对象，所以出现了上文的情况。从上面的源码可以看出，valueOf()在返回之前，会进行判断，判断当前 i的值是否在 -128到127之间。如果存在，则直接返回引用，不再重新开辟内存空间。如果不存在，就创建一个新的对象。利用缓存，这样做既能提高程序执行效率，还能节约内存。

Integer a= 12; Integer b = 12; 因为 IntegerCache中已经存在此对象，直接返回引用，引用相等并且都指向缓存中的数据，所以这时候a == b返回true。

Integer c = 128; Integer d = 128;因为c，d的值大于127，不在[-128, 127]范围内，所以虚拟机会在堆中重新new一个 Integer对象来存放128，创建两个对象就会产生两个这样的空间。两个空间的地址不同，返回到栈中的引用的值也就不同，所以这时候i1 == i2返回false。

源码yyds，但我真的是个菜鸡！

好了，今天的分享就到这了，非常感谢你能看到这里！如果能为你提供哪怕一丁点帮助，都是我的荣幸！有任何不足和错误之处，欢迎指正。

 再次感谢大家！晚安！

参考文档：

Java中Integer.valueOf()解读_shboli的博客-CSDN博客_integer.valueof()作用
我写了套框架，把滑动窗口算法变成了默写题