leetCode算法发现地址变了导致的坑（242. 有效的字母异位词）

灰太狼 2024-04-03 12:01 28阅读 0赞

## 一、概述 ##

最近做这个算法题，发现了一个坑：  
`https://leetcode.cn/problems/valid-anagram/`

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
    
    注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
    
    来源：力扣（LeetCode）
    链接：https://leetcode.cn/problems/valid-anagram
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

***37个测试用例，过了36个，有一个没有过。***

![在这里插入图片描述][df6422a3184d4f5988fbfa4af17ace1f.png]

下面是本人的答案代码：

class Solution {
         public boolean isAnagram(String s, String t) {
    
    
    
            Map<Character,Integer> maps = new HashMap<Character,Integer>();
            Map<Character,Integer> mapt = new HashMap<Character,Integer>();
    
            for(int i=0;i<s.length();i++){
                char cs = s.charAt(i);
                if(maps.get(cs)!=null){
                    int count = maps.get(cs);
                    count++;
                    maps.put(cs,count);
                }else{
                    maps.put(cs,1);
                }
            }
    
            for(int i=0;i<t.length();i++){
                char cs = t.charAt(i);
                if(mapt.get(cs)!=null){
                    int count = mapt.get(cs);
                    count++;
                    mapt.put(cs,count);
                }else{
                    mapt.put(cs,1);
                }
            }
    
    
            Set<Character> sSet = maps.keySet();
            Set<Character> tSet = mapt.keySet();
            if(sSet.size()!=tSet.size()){
                return false;
            }else{
                for(Character ff : sSet){
                    /*正确解法
                    int a = maps.getOrDefault(ff,0);
                    int b = mapt.getOrDefault(ff,0);
                    if(a!=b){
                        return false;
                    }
                    */
                    //有问题的解法
                    if(maps.get(ff)!=mapt.get(ff)){
                        return false;
                    }
                }
            }
    
            return true;
        }
    }

***感觉比较神奇，也不是判空或者0导致的没有通过之类的。***

## 二、分析 ##

本地调试了一番，问题在这里（简化后）：

public static void main(String[] args) {
    
            HashMap<Character, Integer> map1 = new HashMap<Character, Integer>();
            HashMap<Character, Integer> map2 = new HashMap<Character, Integer>();
    
            map1.put('a',127);
            map2.put('a',127);
    
            map1.put('b',128);
            map2.put('b',128);
    
            Integer a1 = map1.get('a');
            Integer a2 = map2.get('a');
    
            Integer b1 = map1.get('b');
            Integer b2 = map2.get('b');
    
            System.out.println(a1==a2);
            System.out.println(b1==b2);
    
        }

这段代码比较简单，看起来控制台应该打印2个true的；***结果打印了一个true，一个false。***  
![在这里插入图片描述][a6139aa59bee442b8786b2f1b0649ab7.png]

多次尝试后发现，***map里放的数字，如果大于127，***那么Integer的地址就会变化，导致了不相等。（原因未知）  
![在这里插入图片描述][fa0e1a46ed0b4fb6b3bc4a350590596e.png]  
如图，  
保存’a’的地址，2个map中都是540，没有问题；  
保存127的地址，2个map中都是533，没有问题；  
保存’b’的地址，2个map中都是541，没有问题；  
***但是，保存128的地址，2个map中一个是534，一个是535，出现了问题。***

## 三、结论 ##

声明map时，泛型传入的Integer(只能是Integer，不能是int，会报错)，***不能直接比较***；  
如果直接比较，比较的是地址，而不是int值；  
如果int值大于127，那么Integer的地址就会不同，比较后就会得到不相等的错误结果。

***从map中取出Integer后，可以转为int，然后再比较就可以了。***

## 四、备注 ##

**IntegerCache类中使用cache\[\]数组缓存了从-128~127共256个Integer对象，所以数字在这个范围时，地址是一样的；如果不在这个范围，就会new一个新Integer对象并返回。**

（意思是，如果`Integer a =128`的话，就会新创建一个对象；`Integer b =128`，也会新创建一个对象；a对象与b对象的地址就会不相同）

相关链接：https://blog.csdn.net/MSSPLANET/article/details/122530816

[df6422a3184d4f5988fbfa4af17ace1f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/21345b3c5a6b446682213f857bb4348c.png
[a6139aa59bee442b8786b2f1b0649ab7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/c6e5ed617ca8421dae510eae381417b7.png
[fa0e1a46ed0b4fb6b3bc4a350590596e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/744ab45d5cc5436591f2912216af9d3a.png