242. 有效的字母异位词

leetcode题目地址

简单题，哈希表。数组长度为常量，因此空间复杂度为O(1)。

时间复杂度： $O(n)$
空间复杂度： $O(1)$

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

349. 两个数组的交集

leetcode题目地址

Set的使用。

时间复杂度： $O(n+m)$
空间复杂度： $O(n)$

// java
class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> hash = new HashSet<>();
        Set<Integer> list = new HashSet<>();
        for(int i=0; i<nums1.length; i++){
            hash.add(nums1[i]);
        }
        for(int i=0; i<nums2.length; i++){
            if(hash.contains(nums2[i])){
                list.add(nums2[i]);
            }
        }
        int[] res = new int[list.size()];
        int idx = 0;
        for(int x : list){
            res[idx++] = x;
        }
        return res;
    }
}

202. 快乐数

leetcode题目地址

多推几步就会发现，不是快乐数的数字经过计算会重复出现。因此借助hash表，重复出现则不是快乐数。

时间复杂度： $O(n)$
空间复杂度： $O(n)$

// java
class Solution {
    public int cal(int n){
        int sum=0;
        while(n!=0){
            int x = n%10;
            n/=10;
            sum += x*x;
        }
        return sum;
    }
    public boolean isHappy(int n) {
        Map<Integer, Integer> hash = new HashMap<>();

        while(n!=1){
            if(hash.containsKey(n))return false;
            hash.put(n, 1);
            n = cal(n);
        }
        return true;
    }
}

1. 两数之和

leetcode题目地址

使用map记录已访问过的元素及对应下标，判断target-当前元素的值是否已访问，若已访问直接返回。

时间复杂度： $O(n)$
空间复杂度： $O(n)$

// java
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        Map<Integer, Integer> hash = new HashMap<>();
        for(int i=0; i<nums.length; i++){
            if(hash.containsKey(target-nums[i])){
                // return {hash.get(target-nums[i]), i};
                res[0] = hash.get(target-nums[i]);
                res[1] = i;
                break;
            }
            hash.put(nums[i], i);
        }
        return res;
    }
}