算法学习Day4——哈希1

在需要判断元素是否重复出现的时候可以考虑使用哈希法。

242 有效的字母异位词

使用数组

核心：使用一个26大小的数组记录每个字母出现的次数，第一次++，第二次--，最后看数组是否全部为0。

class Solution {
    public boolean isAnagram(String s, String t) {
        int[] record =new int[26];
        for(int i=0;i<s.length();i++){
            record[s.charAt(i) - 'a']++;
        }
        for(int i=0;i<t.length();i++){
            record[t.charAt(i) - 'a']--;
        }
        for(int count:record){
            if(count!=0){
                return false;
            }
        }
        return true;

    }
}

349 两个数组的交集

由于没有数值大小，所以不用数组来做哈希表，使用hashset。

最后结果输出有两种方式：1.转化成数组。 2.重新申请一个数组来存放。

import java.util.HashSet;
import java.util.Set;
class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set1= new HashSet<>();
        Set<Integer> resSet=new HashSet<>();
        for(int i:nums1){
            set1.add(i);
        }
        for(int i:nums2){
            if(set1.contains(i)){
                resSet.add(i);
            }
        }
        return resSet.stream().mapToInt(x->x).toArray();

    }
}

202 快乐数

关键是看sum和会不会重复出现。还有就是求每个数字的平方和的操作。

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> record= new HashSet<>();
        while(n!=1 && !record.contains(n)){
            record.add(n);
            n=getNextNumber(n);
        }
        return n==1;

    }
    private int getNextNumber(int n){
        int res =0;
        while(n >0){
            int temp= n%10;
            res += temp*temp;
            n = n/10;
        }
        return res;
    }
}

两数之和

使用map

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] res =new int[2];
        Map<Integer,Integer> map =new HashMap<>();
        for(int i=0;i<nums.length;i++){
//找map里面有没有存符合的
            int temp=target-nums[i];
            if(map.containsKey(temp)){
                res[1]=i;
                res[0]=map.get(temp);
                break;
            }
            map.put(nums[i],i); //如果没有就存进去
        }
        return res;

    }
}