每日一道numJewelsInStone

今天这道宝石与石头问题，也就是字符串S代表石头，J代表宝石，要在S里找到和J相同的的数量，也就是在石头里找到宝石的个数

1.按照暴力解法，（循环S 然后循环J 有相同的字符count++）

public static int numJewelsInStone1(String J ,String S){
        char[] a = S.toCharArray();
        char[] b = J.toCharArray();
        int count = 0 ;
        if(a.length >50){
            return 0;
        }
        for(int i = 0; i <S.length(); i++){
            for(int j =0 ;j < J.length();j++){
                if(b[j] == a[i]){
                    count ++;
                }
            }
        }
        return count;
    }

个人觉得，这种暴力解法很简单，但是效率低 嵌套两次时间复杂度O（n2）leetcode也耗时21ms
可以参考之前的两数之和的解法，利用HashMap 只需要一次循环即可

2.利用hashMap

public static int numJewelsInStone2(String J ,String S){
        char[] a = S.toCharArray();
        char[] b = J.toCharArray();
        int count = 0;
        if(a.length > 50){
            return 0;
        }
        Map<Character,Integer> map = new HashMap<>();
        for(int i = 0; i < J.length(); i ++){
            map.put(b[i],i);
        }

        for(int j = 0; j <S.length(); j++){
          //通过比较键值来确定S里包含J
            if(map.containsKey(a[j])){
                count ++;
            }

        }
        return count;
    }

总结：这是一道很简单的题，我们一般会想到暴力解法，但是效率低 最终在Leetcode比较后者比前者提升9ms

QQ图片20190108212306.png