《代码随想录》刷题笔记——哈希表篇【java实现】

有效的字母异位词

https://leetcode.cn/problems/valid-anagram/submissions/

【思路】

因为单词是由字母组成的，可以直接通过ASCII将字母看成是数字

public boolean isAnagram(String s, String t) {
    // 因为参数里面都是小写字母，因此只需要创建长度为26的数组即可
    int[] arr = new int[26];

    // 统计字符串1的每个字母的个数
    for (int i = 0; i < s.length(); i++) {
        arr[s.charAt(i) - 'a'] += 1;
    }

    // 遍历字符串2，将相应的字母个数减少
    for (int i = 0; i < t.length(); i++) {
        arr[t.charAt(i) - 'a'] -= 1;
    }

    // 如果有哪个字母的数量不为零，就足以说明两个字符串的字母个数不太相同
    for (int num : arr) {
        if (num != 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

• 时间复杂度: O(n)
• 空间复杂度: O(1)

两个数组的交集

使用Hash数组

可以用一个数组来记录元素的次数，但是如果数字的范围很大，就不建议使用这种方法了，因为会非常浪费内存

public int[] intersection(int[] nums1, int[] nums2) {
    int[] arr = new int[1001];
    // 将nums1中有的元素的数量设置为1
    for (int num1 : nums1) {
        if (arr[num1] == 0) {
            arr[num1]++;
        }
    }

    // 将 nums1和nums2 共有的数字数量设置为2，并记录数字为2的数量
    int resultLen = 0;
    for (int num2 : nums2) {
        if (arr[num2] == 1) {
            arr[num2]++;
            resultLen++;
        }
    }

    // 将数字为2对应的下标拿出来存储到结果集合中
    int[] result = new int[resultLen];
    int i = 0;
    for (int j = 0; j < arr.length; j++) {
        if (arr[j] == 2) {
            result[i++] = j;
        }
    }
    return result;
}
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

使用HashSet

直接使用HashSet来记录nums1的元素，然后遍历nums2，判断HashSet里面有没有即可，如果有的话，就添加到结果集中

public int[] intersection1(int[] nums1, int[] nums2) {
    HashSet<Integer> set = new HashSet<>();
    HashSet<Integer> result = new HashSet<>();
    for (int num1 : nums1) {
        set.add(num1);
    }

    for (int num2 : nums2) {
        if (set.contains(num2)) {
            result.add(num2);
        }
    }

    return result.stream().mapToInt(item -> item).toArray();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

快乐数

https://leetcode.cn/problems/happy-number/

【思路】

该题主要是需要使用set来判断一个数字是否存在重复的情况，如果存在重复，那一定会陷入无限循环，直接返回false即可

public static boolean isHappy(int n) {
    // 用来存储总和，如果陷入无限循环，sum会重复
    HashSet<Integer> sumSet = new HashSet<>();

    while (true) {
        int sum = 0;
        while (n > 0) {
            // 取出末尾那个数字
            int num = n % 10;
            sum += num * num;
            // 去掉末尾的数字
            n = n / 10;
        }
        if (sum == 1) {
            return true;
        } else {
            if (sumSet.contains(sum)) {
                return false;
            }
            sumSet.add(sum);
            n = sum;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

两数之和

https://leetcode.cn/problems/two-sum/

【思路】

• 使用一个字典来存储已经遍历过的元素及其下标，等遍历到一个元素的时候，判断map中是否存在(target-元素)的键即可，如果存在，即可直接返回下标数组
• 因为下标没有顺序，直接用HashMap即可，如果有顺序的话，那就需要用LinkedHashMap

public int[] twoSum(int[] nums, int target) {
    HashMap<Integer, Integer> numAndIndexMap = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int num = nums[i];
        if (numAndIndexMap.containsKey(target - num)) {
            return new int[]{i, numAndIndexMap.get(target - num)};
        } else {
            numAndIndexMap.put(num, i);
        }
    }
    return null;
}
1
2
3
4
5
6
7
8
9
10
11
12

四数相加

https://leetcode.cn/problems/4sum-ii/

【思路】

• 如果直接使用四层循环，时间复杂度太高了，可以使用HashMap来存储(num1+num2)及其数量
• 在使用两层循环遍历nums3、nums4，使用一个count来实时记录数量即可，num+=map.get(0-num3-num4)

public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
    HashMap<Integer, Integer> sumOfNum1Num2AndNumberMap = new HashMap<>();
    for (int num1 : nums1) {
        for (int num2 : nums2) {
            int sum = num1 + num2;
            if (!sumOfNum1Num2AndNumberMap.containsKey(sum)) {
                sumOfNum1Num2AndNumberMap.put(sum, 1);
            } else {
                sumOfNum1Num2AndNumberMap.put(sum, sumOfNum1Num2AndNumberMap.get(sum) + 1);
            }
        }
    }

    int count = 0;
    for (int num3 : nums3) {
        for (int num4 : nums4) {
            if (sumOfNum1Num2AndNumberMap.containsKey(0 - num3 - num4)) {
                count += sumOfNum1Num2AndNumberMap.get(0 - num3 - num4);
            }
        }
    }
    return count;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

赎金信

https://leetcode.cn/problems/ransom-note/

【思路】

这道题很容就想到使用map来存储magazine的字符及其数量，但是很容易漏掉一个细节，那就是单词都是由小写字母组成的，这时使用一个长度为26的数组来存储数量会更加好，因为使用map的空间消耗比数组更大，因为map要维护红黑树或哈希表，还需要做哈希函数

【使用map实现】

public boolean canConstruct(String ransomNote, String magazine) {
    HashMap<Character, Integer> map = new HashMap<>();
    for (int i = 0; i < magazine.length(); i++) {
        char c = magazine.charAt(i);
        if (!map.containsKey(c)) {
            map.put(c, 1);
        } else {
            map.put(c, map.get(c) + 1);
        }
    }
    for (int i = 0; i < ransomNote.length(); i++) {
        char c = ransomNote.charAt(i);
        if (map.containsKey(c)) {
            Integer num = map.get(c);
            if (num == 1) {
                map.remove(c);
            } else {
                map.put(c, map.get(c) - 1);
            }
        } else {
            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

【使用数组来实现】

public boolean canConstruct1(String ransomNote, String magazine) {
    int[] arr = new int[26];
    for (int i = 0; i < magazine.length(); i++) {
        char c = magazine.charAt(i);
        arr[c - 'a']++;
    }
    for (int i = 0; i < ransomNote.length(); i++) {
        char c = ransomNote.charAt(i);
        if (arr[c - 'a'] > 0) {
            arr[c - 'a']--;
        } else {
            return false;
        }
    }
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

三数之和

https://leetcode.cn/problems/3sum/description/

【双指针法】

• 先升序排序
• 然后写一个循环来遍历数组的前 n-2 个元素来作为三元组的第一个元素，第二、第三个元素使用双指针方法来同时寻找出来，这样算法整体的时间复杂度是O(n^2)
• 该题的关键是如何去重，只要三元组里面的元素都一样，无论顺序怎么样都算是重复

public List<List<Integer>> threeSum(int[] nums) {
  List<List<Integer>> result=new ArrayList();
  // 升序排序
  Arrays.sort(nums);
  int left,right;
  for(int i=0;i<nums.length-2;i++){
    // 如果第一个元素都已经大于0，因为数组是递增顺序的，肯定没有对应的三元组
    if (nums[i] > 0) { 
        return result;
    }
    // 对三元组中的第一个元素进行去重
    if (i > 0 && nums[i] == nums[i - 1]) {
      continue;
    }
    left=i+1;
    right=nums.length-1;
    while(left<right){
      if(nums[i]+nums[left]+nums[right]>0){
        right--;
      }else if(nums[i]+nums[left]+nums[right]<0){
        left++;
      }else{
        List<Integer> group=new ArrayList();
        group.add(nums[i]);
        group.add(nums[left]);
        group.add(nums[right]);
        result.add(group);
        // 对第三个元素进行去重
        while (right > left && nums[right] == nums[right - 1]) right--;
        // 对第二个元素进行去重
        while (right > left && nums[left] == nums[left + 1]) left++;
        right--;
        left++;
      }
    }
  }
  return result;
}
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
36
37
38

四数之和

https://leetcode.cn/problems/4sum/description/

【说明】

该题还是可以使用双指针法，其实和三数之和类似的，三数之后是遍历第一个元素，然后双指针处理后面两个元素；四数之和就是遍历前两个元素，双指针处理后面两个元素。如果有五数之和、六数之和，也是类似的方法，多遍历前面的元素而已。因此双指针法只是比暴力遍历求解少了一层遍历，即将时间复杂度从O(n)变为O(n-1)

public static List<List<Integer>> fourSum(int[] nums, int target) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(nums);
    for (int i = 0; i < nums.length - 3; i++) {
        // nums[i]必须要大于0，不然当nums是{1, -2, -5, -4, -3, 3, 3, 5}，target是-11，就会不满足
        if (nums[i] > 0 && nums[i] > target) {
            return result;
        }
        if (i > 0 && nums[i] == nums[i - 1]) {
            // 去重
            continue;
        }
        for (int j = i + 1; j < nums.length - 2; j++) {
            // 不加j > i + 1的话，nums=[-2,-1,-1,1,1,2,2], target=0这个案例会出现问题
            if (j > i + 1 && nums[j] == nums[j - 1]) {
                // 去重
                continue;
            }
            int left = j + 1;
            int right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[j] + nums[left] + nums[right];
                if (sum > target) {
                    right--;
                } else if (sum < target) {
                    left++;
                } else {
                    result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                    while (left < right && nums[left + 1] == nums[left]) {
                        left++;
                    }
                    while (left < right && nums[right - 1] == nums[right]) {
                        right--;
                    }
                    right--;
                    left++;
                }
            }
        }
    }
    return result;
}
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
36
37
38
39
40
41
42