LeetCode——哈希表（Java）

简介

记录一下自己刷题的历程以及代码。写题过程中参考了 代码随想录。会附上一些个人的思路，如果有错误，可以在评论区提醒一下。

什么类型的题应该是用哈希表的思想？
需要快速判断一个元素是否出现集合里时。

[简单] 242. 有效的字母异位词

原题链接

最容易想到的就是开两个 26 大小的数组分别做字符统计，然后比较，稍微简化一些可以在单个数组上做统计比对。
这道题放在哈希表系列之下，我想s.charAt(i) - 'a'就是一种hashFunction()，把每个字符对应到一个数组下标从而进行统计

class Solution {
    public boolean isAnagram(String s, String t) {
        int[] count = new int[26];
        for(int i = 0; i < s.length(); i++){
            count[s.charAt(i) - 'a']++;
        }
        for(int i = 0; i < t.length(); i++){
            count[t.charAt(i) - 'a']--;
        }
        for(int i = 0; i < 26; i++){
            if(count[i] != 0) return false;
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

[简单] 349. 两个数组的交集

原题链接

方法①：使用HashSet 写起来方便，效率比较低

class Solution {
     public int[] intersection(int[] nums1, int[] nums2)  {
        HashSet<Integer> set1 = new HashSet<>();
        HashSet<Integer> set2 = new HashSet<>();
        for( int i : nums1){
            set1.add(i);
        }
        for( int i : nums2){
            if(set1.contains(i)){
                set2.add(i);
            }
        }
        return set2.stream().mapToInt(x -> x).toArray();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

方法②：List + 数组遍历

public int[] intersection(int[] nums1, int[] nums2)  {
        int[] count1 = new int[1001];
        int[] count2 = new int[1001];
        List<Integer> ansList = new ArrayList<>();
        for(int i = 0; i < nums1.length; i++){
            count1[nums1[i]]++;
        }
        for(int i = 0; i < nums2.length; i++){
            if(count1[nums2[i]] != 0 && count2[nums2[i]] == 0){
                count2[nums2[i]]++;
                ansList.add(nums2[i]);
            }
        }
        int ans[] = new int[ansList.size()];
        int index = 0;
        for(int i : ansList){
            ans[index++] = i;
        }
        return ans;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

方法①和方法②的效率差距：

[简单] 202. 快乐数

原题链接

题目中说不是快乐数的情况下，sum会一直循环，也就是当sum重复出现的时候，他就不会是一个快乐数了（这个我感觉题面上给的不是很直接），那么只要对sum出现的情况做统计，就可以判断n是否是快乐数。

方法①：在数组上进行统计，int类型最大值 2147483645 最大的情况下也就是十位数，每一位平方总和不会大于 9 * 9 *10;

class Solution {
    public boolean isHappy(int n) {
        int[] count = new int[850];
        while(n != 1){
            int sum = 0;
            while(n > 0){
                sum += (n % 10) * (n % 10);
                n = n / 10;
            }
            if(count[sum] != 0) return false;
            count[sum]++;
            n = sum;
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

方法②：利用HashSet做统计，HashSet不会储存重复的元素。

class Solution {
    public boolean isHappy(int n) {
        HashSet<Integer> set = new HashSet<>();
        while(n != 1){
            int sum = 0;
            while(n > 0){
                sum += (n % 10) * (n % 10);
                n = n / 10;
            }
            if(set.contains(sum)) return false;
            set.add(sum);
            n = sum;
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

[简单] 1. 两数之和

原题链接

题目已经给定了样例情况只会有一对正确答案，所以整体上不需要多少边界判断，也可以自己适当做一些细化的处理。

方法①：最简单的思路就是二重循环遍历判断，时间效率上肯定比较低，时间复杂度O(n^2)。

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

方法②：使用HashMap映射，遍历每个元素的时候去map中查找target - nums[i]是否已经在map中，有则返回，否则放入当前元素，继续遍历，时间复杂度O(n)。

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

方法①和方法②的效率差距：

[中等] 454. 四数相加 II

原题链接

暴力解法的话，四重循环时间复杂度是O(n^4)，这显然不太合适。
跟上面一题思路类似，当考虑nums1[i] + nums2[j]中的i和j是否是一组答案中的一部分时，考虑是否有nums3[i] + nums4[j]是前者的相反数即可。所以只需要对nums1和nums2做二重循环记录所有的相加的结果，再到nums3和nums4中做二重循环，看相反数是否包含在上面的记录中。
使用HashMap时，本题不需要记录下标，所以map中的value可以设置为这一组值出现的次数，（map不记录重复的key)。

public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        HashMap<Integer ,Integer> map = new HashMap<>();
        int count = 0;
        for(int i = 0; i < nums1.length; i++){
            for(int j = 0; j < nums2.length; j++){
                if(map.containsKey(nums1[i] + nums2[j]))
                    map.put(nums1[i] + nums2[j], map.get(nums1[i] + nums2[j]) + 1);
                else map.put(nums1[i] + nums2[j], 1);
            }
        }
        for(int i = 0; i < nums3.length; i++) {
            for (int j = 0; j < nums4.length; j++) {
                if(map.containsKey(0 - nums3[i] - nums4[j]))
                    count += map.get(0 - nums3[i] - nums4[j]);
            }
        }
        return count;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

[简单] 383. 赎金信

原题链接
思维惯性想到HashMap，因为上面的题写多了，但其实这题简单题直接用数组统计就行了。
代码随想录：

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

[中等] 15. 三数之和

原题链接

代码随想录——题解

这题用哈希表的思想很难去重，不如用双指针法。先对数组进行排序，一轮循环中，给定left = i + 1;right = nums.length - 1;此时，三数之和大于0则right--，三数之和小于0则left++。
去重的思路就抓住一个，在三个指针移动的时候跳过后续碰到的相同的数。可以用[-4,-1,-1,-1,0,0,1,1,2,2]手动模拟一下。
注意找到答案的时候也需要移动指针，不能直接退出当前循环，因为有可能有[-1,-4,-3,4,5],[-1,-4,5]找到时，还需要继续去找[-1,-3,4]

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> answer = new ArrayList<>();
        Arrays.sort(nums);
        for(int i = 0; i < nums.length ; i++){
            if(nums[i] > 0) break;
            //去重
            if(i > 0 && nums[i] == nums[i - 1])
                continue;
            int left = i + 1;
            int right = nums.length - 1;
            while(left < right) {
                //总和过大，right左移
                if (nums[i] + nums[left] + nums[right] > 0) {
                    while(left < right && nums[right - 1] == nums[right]) right--;
                    right--;
                }else if(nums[i] + nums[left] + nums[right] < 0){
                    while(left < right && nums[left + 1] == nums[left]) left++;
                    left ++;
                }else{
                    answer.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    while(left < right && nums[right - 1] == nums[right]) right--;
                    right--;
                }
            }
        }
        return answer;
    }
}
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

[中等] 18. 四数之和

原题链接

排序 + 双指针

在三数之和的基础上再加一组循环，做好去重操作，要注意和相加为0的情况不同，相加为0时一旦出现nums[i] > 0就可以跳过本次循环，因为剩下的数加进来只会更大，但是如果target是负数的情况下，哪怕nums[i] > target,再加入其他负数也有可能让总和变小，因此，无法跳过。

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> answer = new ArrayList<>();
        if(nums.length < 4) return answer;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 3 ; i++){
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;//去重
            }
            for (int j = i + 1; j < nums.length - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;//去重(j 和 i 可以重复，要避开 j == i + 1 的情况
                }
                int left = j + 1;
                int right = nums.length - 1;
                while (left < right) {
                    //防止溢出
                    long sum = (long)nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum > target) {
                        //总和过大，right左移，同时去重
                        while (left < right && nums[right - 1] == nums[right]) right--;
                        right--;
                    } else if (sum < target) {
                        //总和过小，left右移，同时去重
                        while (left < right && nums[left + 1] == nums[left]) left++;
                        left++;
                    } else {
                        //添加答案
                        answer.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        while (left < right && nums[right - 1] == nums[right]) right--; //去重
                        right--;
                    }
                }
            }
        }
        return answer;
    }
}
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

防止数据溢出，四个1000000000相加超过int数据范围会变成负数，
long sum = (long)nums[i] + nums[j] + nums[left] + nums[right];