一个奇怪的 Java HashMap 问题

黑白
  • 129

最近在leet刷题的过程中遇到了一个奇怪的HashMap 问题,
567. 字符串的排列

第一次提交代码:

class Solution {
    public boolean checkInclusion(String s1, String s2) {
            Map<Character ,Integer> need=new HashMap<>();
            Map<Character ,Integer> window=new HashMap<>();
            for(int i=0;i<s1.length();i++){
                char s =s1.charAt(i);
                need.put(s,need.getOrDefault(s,0)+1);
            }

            int left=0 , right=0 ,valid=0;
            while(right<s2.length()){
                char c =s2.charAt(right);
                right++;
                if(need.containsKey(c)){
                     window.put(c,window.getOrDefault(c,0)+1);
                     if(need.get(c)==window.get(c)){
                         valid++;
                     }
                }

                while(valid==need.size()){
                    if(right-left==s1.length()){
                        return true;
                    }    
                    char d =s2.charAt(left);
                    left++;
                    if(need.containsKey(d)){
                        window.put(d,window.get(d)-1);
                        if(window.get(d)<need.get(d)){
                            valid--;
                        }
                    }
                }
            }

           return false;

    }
}

卡在101 个用例

用例

此时进行调试发现: 从 need.get(c)==window.get(c) 部份比较失效了;

一下使用debug 以 'a' 为例进行追踪:
事先统计 need 中a 的数目为 141 ,使用idea 进行条件dedug;
打印此时 need ,window 中a 的数目:

image.png

image.png

发现当 window.get('a')==window.get('a') 时没有输出true;

解决: 修改window.get(c)==need.get(c),使用int 类型去接收一下就能通过所有样例

             if(need.containsKey(c)){                    
                     window.put(c,window.getOrDefault(c,0)+1);
                    int needNumber=need.get(c);
                    int windowNumber=window.get(c);
                     if(needNumber==windowNumber){                                                
                         valid++;
                     }
                }

完整代码

class Solution {
    public boolean checkInclusion(String s1, String s2) {
            if(s1.length()>s2.length()) return false;

            Map<Character ,Integer> need=new HashMap<>();
            Map<Character ,Integer> window=new HashMap<>();
            for(int i=0;i<s1.length();i++){
                char s =s1.charAt(i);
                need.put(s,need.getOrDefault(s,0)+1);
            }

            int left=0 , right=0 ,valid=0;
            while(right<s2.length()){

                char c =s2.charAt(right);
                right++;
               
                if(need.containsKey(c)){                    
                     window.put(c,window.getOrDefault(c,0)+1);
                    int needNumber=need.get(c);
                    int windowNumber=window.get(c);
                     if(needNumber==windowNumber){                        
                      //   System.out.println(c+" "+need.get(c));
                        
                         valid++;
                     }
                }

                
                while(valid==need.size()){                
                    if(right-left==s1.length()){
                        return true;
                    }    
                    char d =s2.charAt(left);
                    left++;
                    if(need.containsKey(d)){
                        
                        if(window.get(d)==need.get(d)){
                            valid--;
                        }
                        window.put(d,window.get(d)-1);
                    }
                }
            }

           return false;

    }
}

有哪为大神来解释一下这是为什么?

回复
阅读 401
1 个回答
✓ 已被采纳

Integer 是包装类型,是个对象,要用 equals 比较的,==比较返回false是正常的

至于为啥141之前的可以……这个是因为 Integer 对自动装箱的对象做了缓存,-128 - 127都会缓存:

// Integer.java
public static Integer valueOf(int i) {
        if (i >= IntegerCache.low && i <= IntegerCache.high)
            return IntegerCache.cache[i + (-IntegerCache.low)];
        return new Integer(i);
    }

所以这个区间的数字,自动装箱时返回的是缓存的对象,你==比较自然会相等,但超过这个区间就是新对象了

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
你知道吗?

宣传栏