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;}
}