代码随想录算法训练营第六天|242.有效的字母异位词、349. 两个数组的交集、202. 快乐数、1. 两数之和

1.哈希表理论基础

文档讲解： 代码随想录

当遇到要快速判断一个元素是否出现在集合中时，要考虑哈希法。但是哈希法牺牲了空间换取了时间，因为要使用额外的数组、set、map来存放数据，才能实现快速的查找。

2.242.有效的字母异位词

题目链接：有效的字母异位词
文档讲解： 代码随想录

思路：新建两个数组存储s和t中字符出现的频率，依次进行比较。我用了之前209.长度最小的子数组的思路。

class Solution {
    public boolean isAnagram(String s, String t) {
        char[] sAr = s.toCharArray();
        char[] tAr = t.toCharArray();

        int sLen = s.length();
        int tLen = t.length();

        int[] ss = new int[128];
        int[] tt = new int[128];

        for(int i = 0; i < sLen; i++){
            ss[sAr[i]]++;
        }

        for(int i = 0; i < tLen; i++){
            tt[tAr[i]]++;
        }

        for(int i = 0; i < 128; i++){
            if(ss[i] != tt[i]){
                return false;
            }
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

标答的思路改进：新建一个数组，记录s中字符出现的频率，数组的大小只需要26就行。数组是一个简单的哈希表，需要把字符映射到数组也就是哈希表的索引下标上。在遍历t的时候，对t中出现的字符映射到哈希表索引上的数值做-1操作。最后检查记录数组的元素是否全为0。

class Solution {
    public boolean isAnagram(String s, String t) {
        int[] record = new int[26];

        int sLen = s.length();
        int tLen = t.length();

        for(int i = 0; i < sLen; i++){
            record[s.charAt(i) - 97]++;
        }

        for(int i = 0; i < sLen; i++){
            record[t.charAt(i) - 97]--;
        }

        //for(variable : collection) statement
        for(int i: record){
            if(i != 0){
                return false;
            }
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

时间复杂度都为O（M+N）

2.349. 两个数组的交集

题目链接：两个数组的交集
文档讲解： 代码随想录

注意点：
（1）nums1 == null 和 nums.length == 0 的区别
nums1 = null 意味着数组变量并没有指向任何有效的数组对象，不占用内存空间，指针为空；
nums.length = 0 意味着nums 是一个有效的数组对象，但数组中并没有任何元素。
（2）使用数组来做哈希的题目是因为题目限制了数值的大小。这道题如果用数组做，思路为统计每个数出现的频率，若某个数字出现的频率在两个数组中都大于0，则该数字属于交集。

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        if(nums1 == null || nums1.length == 0 || nums2.length == 0 || nums2 == null){
            return new int[0];
        }

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

        //将结果集合转变为数组
        //方法1
        //return resSet.stream().mapToInt(x -> x).toArray();

        //方法2
        int[] arr = new int[resSet.size()];
        int j = 0;
        for(int i : resSet){
            arr[j++] = i;
        }
        return arr;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

3.202. 快乐数

题目链接：快乐数
文档讲解： 代码随想录

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

    private int getSum(int n){
        int res = 0;
        while(n > 0){
            int temp = n % 10;
            res += temp * temp;
            n = n / 10; 
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

4.1. 两数之和

题目链接：两数之和
文档讲解： 代码随想录

//暴力求解
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] arr = new int[2];
        for(int i = 0; i < nums.length - 1; i++){
            for(int j = i + 1; j < nums.length; j++){
                if(nums[i] + nums[j] == target){
                    arr[0] = i;
                    arr[1] = j;
                }
            }
        }
        return arr;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

（1）为什么会想到用哈希表
需要查询一个元素是否出现过，或者一个元素是否在集合中。在此题中，对于元素A，我们需要找是否存在另一个元素B，使得A + B =9。
（2）哈希表为什么用map
由于题目需要返回下标，则需要记录值与下标，需要使用key value结构来存放，key放值，value放下标。map用来存放我们遍历访问过的元素。

//哈希表
class Solution {
    public int[] twoSum(int[] nums, int target) {
        //哈希表
        int[] res = new int[2];
        if(nums == null || nums.length == 0){
            return res;
        } 

        Map<Integer, Integer> map = new HashMap<>();

        for(int i = 0; i < nums.length; i++){
            int temp = target - nums[i];
            if(map.containsKey(temp)){
                res[0] = i;
                res[1] = map.get(temp);
                break;
            }
            map.put(nums[i], i);
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23