算法——哈希表篇

1、哈希表理论基础

哈希表

哈希表是根据关键码的值而直接进行访问的数据结构。哈希表英文名称为hash table又称散列表。

其实数组就是一张哈希表。哈希表中关键码就是数组的索引下标，然后通过下标直接访问数组中的元素，如下图所示：

那么哈希表能解决什么问题呢，一般哈希表都是用来快速判断一个元素是否出现集合里。

例如要查询一个名字是否在这所学校里。

要枚举的话时间复杂度是O(n)，但如果使用哈希表的话， 只需要O(1)就可以做到。

我们只需要初始化把这所学校里学生的名字都存在哈希表里，在查询的时候通过索引直接就可以知道这位同学在不在这所学校里了。

将学生姓名映射到哈希表上就涉及到了hash function ，也就是哈希函数。

哈希函数

哈希函数，把学生的姓名直接映射为哈希表上的索引，然后就可以通过查询索引下标快速知道这位同学是否在这所学校里了。

哈希函数如下图所示，通过hashCode把名字转化为数值，一般hashCode是通过特定编码方式，可以将其他数据格式转化为不同的数值，这样就把学生名字映射为哈希表上的索引数字了。

如果hashCode得到的数值大于 哈希表的大小了，也就是大于tableSize了，怎么办呢？

此时为了保证映射出来的索引数值都落在哈希表上，我们会在再次对数值做一个取模（模数就是数组长度）的操作，就要我们就保证了学生姓名一定可以映射到哈希表上了。

此时问题又来了，哈希表我们刚刚说过，就是一个数组。

如果学生的数量大于哈希表的大小怎么办，此时就算哈希函数计算的再均匀，也避免不了会有几位学生的名字同时映射到哈希表 同一个索引下标的位置。

接下来哈希碰撞登场

哈希碰撞

如图所示，小李和小王通过哈希函数都映射到了索引下标 1 的位置，这一现象叫做哈希碰撞。

一般哈希碰撞有两种解决方法， 拉链法和线性探测法。

拉链法

刚刚小李和小王在索引1的位置发生了冲突，发生冲突的元素都被存储在链表中。 这样我们就可以通过索引找到小李和小王了

（数据规模是dataSize， 哈希表的大小为tableSize）

其实拉链法就是要选择适当的哈希表的大小，这样既不会因为数组空值而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间。

线性探测法

使用线性探测法，一定要保证tableSize大于dataSize（数组长度大于数据数量）。 我们需要依靠哈希表中的空位来解决碰撞问题。

例如冲突的位置，放了小李，那么就向下找一个空位放置小王的信息。所以要求tableSize一定要大于dataSize ，要不然哈希表上就没有空置的位置来存放 冲突的数据了。如图所示：

常见的三种哈希结构

数组、Collection、Map

当我们想使用哈希法来解决问题的时候，我们一般会选择如下三种数据结构。

• 数组：上面已经说过了
• Collection（集合List/Set）：单列集合，List有序可重复，Set无序不可重复，常用实现类ArrayList、HashSet等。
• Map(映射)：双列集合，键值对key-value，常用实现类HashMap等。

总结

总结一下，当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。

但是哈希法也是牺牲了空间换取了时间，因为我们要使用额外的数组，Collection或者是Map来存放数据，才能实现快速的查找。

2、有效的字母异位词

242.有效的字母异位词

力扣题目链接

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

示例 1: 输入: s = “anagram”, t = “nagaram” 输出: true

示例 2: 输入: s = “rat”, t = “car” 输出: false

说明: 你可以假设字符串只包含小写字母。

思路

第一种思路：将字符串转为字符数组，通过工具类将两个数组排序，判断排序后的两个数组是否相等即可。

第二种思路：使用数组当作简单哈希表，而且这道题目中字符串只有小写字符，那么就可以定义一个数组，来记录字符串s里字符出现的次数。【索引下标代表每一个字符，索引位置数字代表字符出现个数】

需要定义一个多大的数组呢，定一个数组叫做records，大小为26 就可以了，默认初始化为0，因为字符a到字符z的ASCII也是26个连续的数值。

为了方便举例，判断一下字符串s= “aee”, t = “eae”。

操作动画如下：

定义一个数组叫做records用来上记录字符串s里字符出现的次数。

需要把字符映射到数组也就是哈希表的索引下标上，因为字符a到字符z的ASCII是26个连续的数值，所以字符a映射为下标0，相应的字符z映射为下标25。【 实际上不需要记住a-z ASCII码值，只需 每个字符- 'a' ，下标就是从零开始】

再遍历 字符串s的时候，只需要将 s[i] - ‘a’ 所在的元素做+1 操作即可，并不需要记住字符a的ASCII，只要求出一个相对数值就可以了。 这样就将字符串s中字符出现的次数统计出来了。

那看一下如何检查字符串t中是否出现了这些字符，同样在遍历字符串t的时候，对t中出现的字符映射哈希表索引上的数值再做-1的操作。

那么最后检查一下，records数组如果有的元素不为零0，说明字符串s和t一定是谁多了字符或者谁少了字符，直接return false。

最后如果records数组所有元素都为零0，说明字符串s和t是字母异位词，return true。

时间复杂度为O(n)，空间上因为定义是的一个常量大小的辅助数组，所以空间复杂度为O(1)。

代码实现

    public boolean isAnagram(String s, String t) {
        //长度不等直接返回false
        if (s.length() != t.length()) {
            return false;
        }

        //字符数组排序过后应该相等
//        char[] ch1 = s.toCharArray();
//        char[] ch2 = t.toCharArray();
//        Arrays.sort(ch1);
//        Arrays.sort(ch2);
//        return Arrays.equals(ch1, ch2);

        //26个小写字母 不需要记住a-z ASCII码值，只需 每个字符 - 'a' ，下标就是从零开始
        //由数组充当哈希表
        int[] records = new int[26];
        for (int i = 0; i < s.length(); i++) {
            records[s.charAt(i) - 'a'] += 1;
        }

        for (int i = 0; i < t.length(); i++) {
            records[t.charAt(i) - 'a'] -= 1;
        }
     
        for (int record : records) {
            if (record != 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
25
26
27
28
29
30
31

3、两个数组的交集

349. 两个数组的交集

力扣题目链接

题意：给定两个数组，编写一个函数来计算它们的交集。

说明： 输出结果中的每个元素一定是唯一的。 我们可以不考虑输出结果的顺序。

思路

由于题目特意说明：输出结果中的每个元素一定是唯一的，也就是说输出的结果的去重的， 同时可以不考虑输出结果的顺序

我们可以使用set这种数据结构，本身set集合中的元素就是被去过重的，只需第一次遍历nums1，将nums1元素放到set集合中，然后第二次遍历nums2时，判断set集合中是否有元素存在即可，如果存在就将元素放到结果中，遍历结束将结果返回即可。

代码实现

    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> ans = new HashSet<>();
        Set<Integer> set = new HashSet<>();
        for (int num : nums1) {
            set.add(num);
        }
        for (int num : nums2) {
            if (set.contains(num)) {
                ans.add(num);
            }
        }

        //将集合转为数组 流式计算
        return ans
                .stream()
                // Integer::intValue -> x -> x 也是OK的
                .mapToInt(Integer::intValue)
                .toArray();

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

其他题目

350.两个数组的交集 II

思路

本题返回的元素不会被去重，因此可以有如下做法：

①可以考虑使用List数据结构，同上，只不过第二次遍历时，同时需要将list集合中元素移除，防止结果重复；

②还可以使用Map哈希进行映射，第一次遍历统计出nums1数组不同数字出现的个数，第二次遍历nums2数组时，就可以根据哈希表中是否存在对应元素，存在就放到结果中，注意一点将元素放到结果中后，哈希表对应元素数量也要对应-1，防止结果元素重复；

③可以先将两个数组使用工具类排个序，然后使用双指针法，哪个数组中的元素小对应指针向后移动一位，当两个数组中元素相等时，将元素放到结果中，此时两个指针都向后移动一位（循环条件就是两个指针都要小于对应数组长度）该做法不需要借助额外空间

代码实现

        //方式一：借助List
//        if (nums1.length < nums2.length) {
//            return getResult(nums1, nums2);
//        } else {
//            return getResult(nums2, nums1);
//        }
        List<Integer> ans = new ArrayList<>();
        //方式二：借助Map
        // key是数字，value是数字出现次数
//        Map map = new HashMap<>();
//        for (int num : nums1) {
//            map.put(num, map.getOrDefault(num, 0) + 1);
//        }
//        for (int num : nums2) {
//            Integer count = map.get(num);
//
//            if (count != null && count > 0){
//                ans.add(num);
//                //--count 先减再赋值，此时数已经-1 ; count-- 先赋值再-1，此时数字还未发生改变
//                map.put(num, --count);
//            }
//        }

        //方式三：将两数组排序，双指针法，不需要借助额外空间
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        //双指针
        int i = 0,j = 0;
        while (i < nums1.length && j < nums2.length){
            if (nums1[i] < nums2[j]) {
                i++;
            }else if (nums1[i] > nums2[j]){
                j++;
            }else {
                ans.add(nums1[i]);
                i++;
                j++;
            }
        }
        return ans.stream().mapToInt(x -> x).toArray();
    }

	//List做法
    public int[] getResult(int[] nums1, int[] nums2) {
        List<Integer> ans = new ArrayList<>();
        List<Integer> cacheNum = new ArrayList<>();

        for (int num : nums1) {
            cacheNum.add(num);
        }
        for (int num : nums2) {
            if (cacheNum.contains(num)) {
                //移除元素，不是移除下标元素
                cacheNum.remove(Integer.valueOf(num));
                ans.add(num);
            }

            if (cacheNum.isEmpty()) {
                break;
            }
        }
        return ans.stream().mapToInt(x -> x).toArray();
    }
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

4、快乐数

202. 快乐数

力扣题目链接

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为 1，那么这个数就是快乐数。

如果 n 是快乐数就返回 True ；不是，则返回 False 。

示例：

输入：19
输出：true
解释：
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

输入：2

输出：false

思路

为什么会无限循环？ 答：找快乐数的过程找到了相同的数，相当于链表成环了，
//因此，题目就演变成了判断链表是否成环
/*
以2为例： 2->4->16->37->58->89->145->42->20
            |__________________________/
所以链表只要成环了就会无限循环下去，此数就不是快乐数
否则只要最后链表末尾元素值为1就是快乐数
1
2
3
4
5
6
7

第一种做法：使用哈希表记录元素，再次出现相同元素说明链表成环 （哈希法）【当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法了】；

第二种：双指针法，fast、slow，fast指针一次移动两个节点，slow指针一次移动一个节点fast指针要是能与slow相遇，说明链表成环（fast指针以一个节点的移动速度在环内追赶slow指针，最后一定会相遇）否则链表不能成环【此题比较特殊，就算不能成环，最后fast也会和slow相遇，由于是快乐数的原因，最后fast = slow = 1】，所以循环条件就是fast != slow，最后判断fast是否等于1，等于1就是快乐数，否则不是快乐数

代码实现

 public boolean isHappy(int n) {
        if(n == 1){
            return true;
        }
       //第一种：使用哈希表记录元素，再次出现相同元素说明链表成环 （哈希法）
    //    List cache = new ArrayList<>();
    //    while(n != 1){
    //        cache.add(n);
    //        n = getNextNum(n);
    //        if (cache.contains(n)){
    //            return false;
    //        }
    //    }
    //    return true;

        //第二种：双指针，fast、slow，fast指针一次移动两个节点，slow指针一次移动一个节点
        //fast指针要是能与slow相遇，说明链表成环（fast指针以一个节点的移动速度在环内追赶slow指针，最后一定会相遇）				//否则链表不能成环【此例就算不能成环，fast也会和slow相遇，因为快乐数的缘故，最后fast = slow = 1】
 		int fast = n ,slow = 0;
        while(fast != slow){
            n = getNextNum(n);
            //指针向后移动一位
            slow = n;
            fast = getNextNum(fast);
            //指针向后移动两位
            fast = getNextNum(fast);
        }
        //快乐数fast = slow = 1，非快乐数 fast = slow != 1
        return fast == 1;
    }

    public int getNextNum(int n){
        int next = 0;
        while (n > 0){
            int num = n % 10;
            next += num * num;
            n /= 10;
        }
        return next;
    }
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

5、两数之和

1. 两数之和

力扣题目链接

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

思路

暴力解法，双重循环；最优解法：哈希法，使用map来存放数据，key用来存放数字，value用来存放数字对应下标（因为我们的结果集需要返回下标），遍历过程中将对应数字和数字对应下标放到map中，在此之前，判断我们当前遍历的这个数的target - 当前这个数是否在map中，如果存在直接将两数下标放到结果中返回即可。

代码实现

 public int[] twoSum(int[] nums, int target) {
        //哈希法：key->数字 value->数字对应下标
        Map<Integer, Integer> map = new HashMap<>();
        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[2];
}
1
2
3
4
5
6
7
8
9
10
11

6、四数相加Ⅱ

454.四数相加II

力扣题目链接

给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。

为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -2^28 到 2^28 - 1 之间，最终结果不会超过 2^31 - 1 。

例如:

输入:

• A = [ 1, 2]
• B = [-2,-1]
• C = [-1, 2]
• D = [ 0, 2]

输出:

2

解释:

两个元组如下:

1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

思路

由于题意说是四个数组，可以使用哈希法，来记录两两数组数字之和，map中key存两个数组数字之和，value存当前数字和出现的次数，下次找另两个数组数字之和时，直接去map中查找是否存在 0- (该两数组数字之和)，如果存在取出value加到结果中即可。

代码实现

    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        int ans = 0;
        int sum;
        //哈希法
        //两两数组元素之和，key是前两个数组元素之和，value是元素之和出现次数
        //两两数组时间复杂度O(n^2)
        Map<Integer, Integer> map = new HashMap<>();
        for (int num1 : nums1) {
            for (int num2 : nums2) {
                sum = num1 + num2;
                map.put(sum, map.getOrDefault(sum, 0) + 1);
            }
        }

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

7、赎金信

383. 赎金信

力扣题目链接

给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。

(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)

注意：

你可以假设两个字符串均只含有小写字母。

canConstruct(“a”, “b”) -> false
canConstruct(“aa”, “ab”) -> false
canConstruct(“aa”, “aab”) -> true

思路

题意中明确说明两个字符串只含有小写字母，小写之母只有二十六个，因此可以使用数组当作哈希表来解决该问题，每个字母 - 'a'当作下标，对应下标代表的数就是该字母出现的次数。第一次遍历ransom字符串，统计字母及字母出现次数，第二次遍历magazines 将数组对应字母出现次数-1，最后一次遍历数组，判断数组中是否有字母对应次数>0，如果存在大于0的字母说明ransom 字符串中有字母出现次数比magazines 字符串出现次数多直接返回false，否则返回true。

代码实现

    public boolean canConstruct(String ransomNote, String magazine) {
        if (ransomNote.length() > magazine.length()) {
            return false;
        }

        //`都是由小写字母组成`，可以使用定长数组当作哈希表，索引是字符ASCII码值，对应值就是字母出现次数
        // 小写字母 - 'a' 索引就是从 0-25
        int[] records = new int[26];
        for (int i = 0; i < ransomNote.length(); i++) {
            records[ransomNote.charAt(i) - 'a'] += 1;
        }

        for (int i = 0; i < magazine.length(); i++) {
            records[magazine.charAt(i) - 'a'] -= 1;
        }

        for (int record : records) {
            if (record > 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
25

8、三数之和

第15题. 三数之和

力扣题目链接

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

注意： 答案中不可以包含重复的三元组。

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]

思路

给定一个数组，求不重复的三元组，先看下面求两数之和为定值

一个数组，先看两个数之和为0，可以先将数组排序，左右双指针法，两数之和小于0左指针移动，两数之和大于0右指针移动，如果相等的话，左右指针同时移动，此时在移动的过程中，如果相邻数字想等直接跳过即可（去重）
1

三数之和，就是在两数之和的基础上外边套个循环找第三个数，第三个数也需要去重，第三个数去重，看当前这个数跟前面一个数是否相等，相等直接跳过，找其余两个数逻辑和上述找两个数为定值一样，所以做法是排序 + 双指针。（三个数都要去重）

代码实现

public List<List<Integer>> threeSum(int[] nums) {
        long start = System.currentTimeMillis();
        List<List<Integer>> ans = new ArrayList<>();

        //暴力法 理论可行，数据量大的话会超时，时间复杂度O(n^3) 4423ms
        int len = nums.length;
//        for (int i = 0; i < len; i++) {
//            for (int j = i + 1; j < len; j++) {
//                for (int k = j + 1; k < len; k++) {
//                    if (nums[i] + nums[j] + nums[k] == 0) {
//                        ArrayList list = new ArrayList<>();
//                        list.add(nums[i]);
//                        list.add(nums[j]);
//                        list.add(nums[k]);
//                        //先将集合排序然后手动去重
//                        Collections.sort(list);
//                        if (!ans.contains(list)) {
//                            ans.add(list);
//                        }
//                    }
//
//                }
//            }
//        }

        //先看两个数之和为0，可以先将数组排序，左右双指针法，两数之和小于0左指针移动，两数之和大于0右指针移动，如果相等的话，左右指针同时移动
        //此时在移动的过程中，如果相邻数字想等直接跳过即可

        // 排序 + 双指针 一个数 与 两个数之和 的和为0 32ms

        Arrays.sort(nums);
        int first;
        int second;
        int third;
        for (int i = 0; i < len; i++) {
            //第一个数
            first = nums[i];
            //第一个数大于0.直接跳出循环返回结果
            if (first > 0) {
                break;
            }

            //这个数，遍历过程中如果相邻元素相等直接跳过即可
            //后一个数与前一个数相同直接跳过，nums[i] == nums[i + 1]判断条件是三元组不能有相同元素题目没这要求
            if (i > 0 && nums[i - 1] == nums[i]) {
                continue;
            }

            //其他两个数
            int target = -first;
            //左右双指针，从第一个数后一个数开始
            int l = i + 1, r = len - 1;
            while (l < r) {
                second = nums[l];
                third = nums[r];
                if (second + third == target) {
                    List<Integer> list = new ArrayList<>();
                    list.add(first);
                    list.add(second);
                    list.add(third);
                    ans.add(list);
                    //左指针遇到相同的数，跳过 指针左移
                    while (l < r && nums[l] == nums[l + 1]) {
                        l++;
                    }
                    //右指针遇到相同的数，跳过 指针右移
                    while (l < r && nums[r] == nums[r - 1]) {
                        r--;
                    }
                    l++;
                    r--;
                } else if (second + third < target) {
                    l++;
                } else {
                    r--;
                }
            }
        }

        System.out.println("it costs time " + (System.currentTimeMillis() - start) + "ms");

        return ans;
    }
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

9、四数之和

第18题. 四数之和

力扣题目链接

题意：给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：

答案中不可以包含重复的四元组。

示例： 给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。 满足要求的四元组集合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]

思路

题目与上面三数之和类似，无非就是找三个数，外边再套一层循环找第四个数，四个数都要去重。去重的过程中一定是自己跟自己（自己代表第几个数）比，相邻元素相等直接跳过，不要不同数字之间比较，题目没有要求数字之间不能相同。

代码实现

 public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        if (nums.length < 4) {
            return ans;
        }
        //类似三数之和？ 排序 + 双指针？
        Arrays.sort(nums);
        long first, second, third, four;
        for (int i = 0; i < nums.length - 3; i++) {
            first = nums[i];
            //去重，找数时，相邻两数相等直接跳过
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            for (int j = i + 1; j < nums.length - 2; j++) {
                second = nums[j];
                //去重 j > i + 1，否则第一次去重时就是第二跟第一个数进行相比了，容易错过相应结果集
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }

                //最后两个数
                long other = target - (first + second);
                int left = j + 1;
                int right = nums.length - 1;
                while (left < right) {
                    third = nums[left];
                    four = nums[right];
                    if (third + four == other) {
                        ans.add(Arrays.asList((int) first, (int) second, (int) third, (int) four));
                        //跳过 去重
                        while (left < right && nums[left] == nums[left + 1]) {
                            left++;
                        }
                        while (left < right && nums[right] == nums[right - 1]) {
                            right--;
                        }
                        left++;
                        right--;
                    } else if (third + four < other) {
                        left++;
                    } else {
                        right--;
                    }
                }

            }
        }
        return ans;
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
43
44
45
46
47
48
49
50

10、总结

本篇我们从哈希表的理论基础到数组、set和map的经典应用，把哈希表的整个全貌完整的呈现给大家。

同时也强调虽然map是万能的，详细介绍了什么时候用数组，什么时候用set。哈希表主要用作快速判断某个元素是否存在集合中。