面试
刷题笔记

哈希表系列

1. 有效的字母异位词
2. 赎金信
- 思路一：暴力解法
- 思路二：哈希表解法
3. 字母异位词分组
4. 两个数组的交集
5. 两个数组的交集||
6. 快乐数
7. 两数之和
- 思路一：暴力解法
- 思路二：哈希表解法
8. 四数相加||
9. 三数之和
10. 四数之和

哈希表是根据关键码的值而直接进行访问的数据结构。

这么这官方的解释可能有点懵，其实直白来讲数组就是一张简单的哈希表哈希表中关键码就是数组的索引下标，然后通过下标直接访问数组中的元素，如下图所示：

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

例如要查询一个名字是否在这所学校里。
要枚举的话时间复杂度是O(n)，但如果使用哈希表的话，只需要O(1)就可以做到。
我们只需要初始化把这所学校里学生的名字都存在哈希表里，在查询的时候通过索引直接就可以知道这位同学在不在这所学校里了。

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

事实上，如果数组是适用的，那么最好就不要用哈希表，因为使用哈希表的空间消耗要比数组大，哈希表可能要维护红黑树而且还要做哈希函数，数据量大的话就能体现出来差别了。

# 1. 有效的字母异位词

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

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

示例 1:

输入: s = "anagram", t = "nagaram"

输出: true

示例 2:

输入: s = "rat", t = "car"

输出: false

提示:

1 <= s.length, t.length <= 5 * 104
s 和 t 仅包含小写字母

解题思路如下：力扣链接 (opens new window)

长度判断：首先判断两个字符串s和t的长度是否相同。如果长度不同，直接返回false，因为不同长度的字符串不可能是字母异位词。

初始化哈希表：初始化一个长度为26的数组record，用于记录每个字母出现的次数差异。这里假设字符串只包含小写字母。

遍历并记录差异：遍历字符串s和t，对于s中的每个字符，将其对应在record数组中的计数增加；对于t中的每个字符，将其对应在record数组中的计数减少。这样做的目的是记录两个字符串中每个字母出现次数的差异。

检查哈希表：遍历record数组，检查是否所有元素都为0。如果所有元素都为0，则说明s和t中每个字符出现的次数相同，它们是字母异位词；如果存在非0元素，说明s和t不是字母异位词。

返回结果：如果record数组所有元素都为0，返回true，否则返回false。

时间复杂度O(N)，其中N是字符串s的长度。这是因为我们需要遍历字符串s和t各一次，每次操作是常数级别的。

哈希表解题代码如下

class Solution {
    public boolean isAnagram(String s, String t) {
        // 判断长度是否相等
        if (s.length() != t.length()) {
            return false;
        }

        // 初始化26个字母的哈希表
        int[] record = new int[26];

        // 遍历字符串s和t
        for (int i = 0; i < s.length(); i++) {
            // 对于s中的字符，相应位置增加
            record[s.charAt(i) - 'a']++;
            // 对于t中的字符，相应位置减少
            record[t.charAt(i) - 'a']--;
        }

        // 检查哈希表是否所有元素都为0
        for (int i = 0; i < 26; i++) {
            if (record[i] != 0) {
                return false; // 如果存在非0元素，说明不是字母异位词
            }
        }

        // 如果哈希表所有元素都为0，说明是字母异位词
        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

# 2. 赎金信

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

示例 1：

输入：ransomNote = "a", magazine = "b"

输出：false

示例 2：

输入：ransomNote = "aa", magazine = "ab"

输出：false

示例 3：

输入：ransomNote = "aa", magazine = "aab"

输出：true

提示：

1 <= ransomNote.length, magazine.length <= 105
ransomNote 和 magazine 由小写英文字母组成

解题思路如下：力扣链接 (opens new window)

# 思路一：暴力解法

遍历 ransomNote：对于 ransomNote 中的每个字符，我们需要在 magazine 中找到相同的字符并标记已使用，以确保 magazine 中的每个字符只被使用一次。

查找并标记：对于 ransomNote 中的每个字符，在 magazine 中遍历查找。如果找到相同字符，标记该字符为已使用（例如，将其替换为特殊字符，以免再次使用）。

判断能否构成：如果在 magazine 中未找到相应字符，或者对应字符已被标记为已使用，则返回 false。如果 ransomNote 中的所有字符都在 magazine 中找到了对应的未使用字符，则返回 true。

时间复杂度为O(n*m)，其中 n 是 ransomNote 的长度，m 是 magazine 的长度。

public class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        char[] magazineArr = magazine.toCharArray();
        
        // 遍历 ransomNote 中的每个字符
        for (char c : ransomNote.toCharArray()) {
            boolean found = false;
            // 在 magazine 中查找相同字符
            for (int i = 0; i < magazineArr.length; i++) {
                if (magazineArr[i] == c) {
                    // 标记为已使用，这里用 '*' 表示已使用的字符
                    magazineArr[i] = '*';
                    found = true;
                    break;
                }
            }
            // 如果没找到或已被使用，则返回 false
            if (!found) {
                return false;
            }
        }
        // 所有字符都被成功找到，返回 true
        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

# 思路二：哈希表解法

构建哈希表：使用哈希表对 magazine 中的每个字符进行计数。哈希表的键是字符，值是该字符出现的次数。

遍历 ransomNote：对 ransomNote 中的每个字符，检查它是否在 magazine 的哈希表中有足够的数量。如果某个字符在哈希表中不存在或数量不足，返回 false。

更新哈希表：每次在 ransomNote 中找到 magazine 的字符时，减少哈希表中该字符的计数。

时间复杂度为O(n + m)，其中 n 是 ransomNote 的长度，m 是 magazine 的长度。

public class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        // 建立一个哈希表存储 magazine 中的字符及其出现次数
        int[] charCount = new int[26]; // 由于只有小写字母，可以用长度为26的数组表示哈希表
        for (char c : magazine.toCharArray()) {
            charCount[c - 'a']++; // 对应字符的计数加一
        }

        // 遍历 ransomNote，检查字符是否在哈希表中有足够的数量
        for (char c : ransomNote.toCharArray()) {
            if (--charCount[c - 'a'] < 0) {
                return false; // 字符数量不足，返回 false
            }
        }

        // 所有 ransomNote 中的字符都在 magazine 中找到了
        return true;
    }
}

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

# 3. 字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:

输入: strs = [""]

输出: [[""]]

示例 3:

输入: strs = ["a"]

输出: [["a"]]

提示：

1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母

解题思路如下：力扣链接 (opens new window)

这道题目的要求是将给定的字符串数组 strs 中的字母异位词分组在一起。字母异位词指的是由相同字母以不同顺序构成的单词，例如 "eat" 和 "tea" 是互为字母异位词。

举例来说，如果 strs = ["eat", "tea", "tan", "ate", "nat", "bat"]，则执行这个过程后，哈希表将变成：

"aet" -> ["eat", "tea", "ate"]
"ant" -> ["tan", "nat"]
"abt" -> ["bat"]

为了实现这个目的，我们可以使用哈希表来进行分组。具体步骤如下：

遍历字符串数组：对数组 strs 中的每个字符串进行操作。

排序字符串：将每个字符串的字母按照字典顺序排序。排序后，所有字母异位词将变为相同的字符串。例如，"eat"、"tea" 和 "ate" 排序后都会变成 "aet"。

使用哈希表分组：创建一个哈希表 map，键是排序后的字符串，值是一个列表，用于存储排序后相同的原始字符串。

添加字符串到哈希表：对于每个排序后的字符串 sortedStr，检查它是否已经作为键存在于哈希表中。如果不存在，就在哈希表中添加这个键，并将其值初始化为一个空列表。然后，将原始字符串 s 添加到这个键对应的列表中

时间复杂度：O(NKlogK)，其中 N 是字符串数组的长度，K 是字符串的最大长度。对每个字符串进行排序需要 O(KlogK) 的时间，总共有 N 个字符串。

哈希表解题代码如下

public class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs == null || strs.length == 0) return new ArrayList<>();
        
        Map<String, List<String>> map = new HashMap<>();
        for (String s : strs) {
            // 将字符串 s 排序
            char[] charArray = s.toCharArray();
            Arrays.sort(charArray);
            String sortedStr = String.valueOf(charArray);

            // 将排序后的字符串作为键，将原始字符串添加到对应的列表中
            if (!map.containsKey(sortedStr)) {
                map.put(sortedStr, new ArrayList<>());
            }
            // 首先通过 map.get(sortedStr) 获取到排序后字符串 sortedStr 对应的列表
            // 然后通过 .add(s) 将原始字符串 s 添加到这个列表中。
            map.get(sortedStr).add(s);
        }

        // 返回哈希表中所有值的集合
        return new ArrayList<>(map.values());
    }
}

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

# 4. 两个数组的交集

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是唯一的。我们可以 不考虑输出结果的顺序 。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]

输出：[2]

示例 2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]

输出：[9,4]

解释：[4,9] 也是可通过的

提示：

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000

解题思路如下：力扣链接 (opens new window)

在寻找两个数组的交集时，我们不关心一个元素在数组中出现了多少次，只关心它是否出现。Set集合能够自动处理重复值，确保每个元素只出现一次。

特殊情况处理：如果任一数组为空，直接返回空数组。

创建两个Set集合：
set1 用于存储 nums1 数组的元素。

resSet 用于存储交集结果。

遍历 nums1：将 nums1 的所有元素添加到 set1 中。

遍历 nums2 并构建结果集：
遍历 nums2，如果 set1 中包含 nums2 的某个元素，则将该元素添加到 resSet 中。

将结果集合转换为数组：
方法1：使用 Java 8 的流 (Stream) 将 Set 转换为数组。

方法2：手动创建数组并填充 resSet 中的元素。

返回结果数组。

时间复杂度：O(n + m)，其中 n 和 m 分别是两个数组的长度。

哈希表解题代码如下

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

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        // 特殊情况处理
        if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
            return new int[0];
        }

        Set<Integer> set1 = new HashSet<>();
        Set<Integer> resSet = new HashSet<>();

        // 将 nums1 中的元素添加到 set1
        for (int num : nums1) {
            set1.add(num);
        }

        // 遍历 nums2，并构建交集结果集
        for (int num : nums2) {
            if (set1.contains(num)) {
                resSet.add(num);
            }
        }

        // 方法1：使用 Java 8 Stream API 转换为数组
        return resSet.stream().mapToInt(x -> x).toArray();

        // 方法2：手动创建数组并填充
        /*int[] arr = new int[resSet.size()];
        int index = 0;
        for (int num : resSet) {
            arr[index++] = num;
        }
        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
36
37

# 5. 两个数组的交集||

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]

输出：[2,2]

示例 2:

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]

输出：[4,9]

提示：

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000

解题思路如下：力扣链接 (opens new window)

这道题要求返回两个数组的交集，并且每个元素出现的次数应与它在两个数组中都出现的次数一致。如果一个元素在两个数组中都出现了多次，那么在结果中这个元素也应该出现多次，次数取决于该元素在两个数组中出现次数的较小值。这意味着交集中元素是可以重复的，只要这些重复反映了两个数组中相应元素的共同出现次数。

我们使用一个 HashMap (countMap) 来存储 nums1 中每个元素出现的次数。

我们遍历 nums2，如果当前元素在 countMap 中的计数大于0，就意味着它在两个数组中都出现过，我们把它加入到结果列表中，并在 countMap 中减少该元素的计数。

最后，我们将结果列表转换为数组格式并返回。

时间复杂度为 O(N1 + N2)，其中 N1 和 N2 分别是两个数组的长度

哈希表解题代码如下

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        // 使用哈希表记录第一个数组中每个元素的出现次数
        Map<Integer, Integer> countMap = new HashMap<>();
        for (int num : nums1) {
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
        }

        // 创建一个列表用于存储交集结果
        List<Integer> resultList = new ArrayList<>();

        // 遍历第二个数组，查找交集
        for (int num : nums2) {
            if (countMap.getOrDefault(num, 0) > 0) {
                resultList.add(num); // 添加到结果列表
                countMap.put(num, countMap.get(num) - 1); // 减少哈希表中的计数
            }
        }

        // 将结果列表转换为数组
        int[] resultArray = new int[resultList.size()];
        int index = 0;
        for (int num : resultList) {
            resultArray[index++] = num;
        }

        return resultArray;
    }
}

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

# 6. 快乐数

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

「快乐数」 定义为：

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

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

示例 1：

输入：n = 19

输出：true

解释：

12 + 92 = 82

82 + 22 = 68

62 + 82 = 100

12 + 02 + 02 = 1

示例 2：

输入：n = 2

输出：false

提示：

1 <= n <= 231 - 1

解题思路如下：力扣链接 (opens new window)

快乐数的定义是这样的：对于一个正整数，不断对其各位数字的平方求和，如果这个过程最终能得到1，则这个数是快乐数；如果这个过程陷入了无限循环但始终达不到1，则这个数不是快乐数。

例如，19是一个快乐数，因为：

1^2 + 9^2 = 82， 8^2 + 2^2 = 68， 6^2 + 8^2 = 100， 1^2 + 0^2 + 0^2 = 1。

解题思路是使用哈希集合来检测数字的平方和是否开始重复，从而判断是否进入了循环。如果进入循环且不等于1，则不是快乐数。

整体的时间复杂度是 O(n)，其中 n 是数字 n 的位数。

哈希表解题代码如下

public class Solution {
    public boolean isHappy(int n) {
        Set<Integer> record  = new HashSet<>(); // 创建一个哈希集合用来存储每一步的数字平方和
        while (n != 1 && !record.contains(n)) { // 当n不为1且n不在集合中时，进入循环
            record .add(n); // 将当前数字n添加到集合中
            n = getNextNumber(n); // 计算n的各个位置的平方和
        }
        return n == 1; // 如果n为1，则说明是快乐数，返回true；否则，返回false
    }

	// 获取这个数各个位置的平方和
    private int getNextNumber(int n) {
        int totalSum = 0;
        while (n > 0) { // 循环直到n等于0
            int tmp = n % 10; // 取出最低位的数字
            n = n / 10; // 移除最低位的数字
            totalSum += tmp * tmp; // 累加平方和
        }
        return totalSum; // 返回总和
    }
}

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

# 7. 两数之和

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9

输出：[0,1]

解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6

输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6

输出：[0,1]

提示：

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案

解题思路如下：力扣链接 (opens new window)

# 思路一：暴力解法

暴力解法的思路是检查数组中的每一对元素，看它们的和是否等于目标值 target。

两层循环遍历数组 nums。外层循环遍历数组中的每个元素，内层循环遍历当前元素之后的每个元素。

在内层循环中，检查外层循环的当前元素 nums[i] 和内层循环的当前元素 nums[j] 的和是否等于 target。

如果找到和为 target 的一对元素，则返回它们的下标。

时间复杂度是 O(n²)，其中 n 是数组 nums 的长度。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // 遍历数组的每一个元素
        for (int i = 0; i < nums.length; i++) {
            // 再遍历当前元素之后的每一个元素
            for (int j = i + 1; j < nums.length; j++) {
                // 检查两个元素的和是否等于目标值
                if (nums[i] + nums[j] == target) {
                    // 如果是，返回它们的下标
                    return new int[] {i, j};
                }
            }
        }
        // 如果没有找到，返回空数组
        return new int[0];
    }
}

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

# 思路二：哈希表解法

使用哈希表解决这个问题的核心思想是：在遍历数组的同时，利用哈希表存储已经遍历过的元素及其下标，这样可以在 O(1) 的时间内判断 target - 当前元素 是否已经在之前出现过。

初始化哈希表：创建一个哈希表用来存储数组中每个元素的值和对应的索引。

遍历数组：遍历数组中的每一个元素。

检查哈希表：对于每个元素，检查 target - 当前元素 是否已经在哈希表中。如果是，返回当前元素的下标和哈希表中 target - 当前元素 的下标。

更新哈希表：将当前元素和它的下标存入哈希表。

时间复杂度：O(n)，只需要遍历数组一次。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // 创建哈希表
        Map<Integer, Integer> map= new HashMap<>();
        // 遍历数组
        for (int i = 0; i < nums.length; i++) {
            // 计算差值
            int tmp = target - nums[i];
            // 检查差值是否已在哈希表中
            if (map.containsKey(tmp)) {
                // 如果找到，返回当前下标和哈希表中差值的下标
                return new int[] {map.get(tmp), i};
            }
            // 将当前元素和其下标存入哈希表
            map.put(nums[i], i);
        }
        return new int[0];
    }
}

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

# 8. 四数相加||

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

示例 1：

输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]

输出：2

解释：

两个元组如下：

(0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0

(1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

示例 2：

输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]

输出：1

提示：

n == nums1.length
n == nums2.length
n == nums3.length
n == nums4.length
1 <= n <= 200
-228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228

解题思路如下：力扣链接 (opens new window)

这个问题可以使用哈希表来优化时间复杂度。基本思路是先计算出数组 nums1 和 nums2 所有可能的元素之和，并将这些和以及对应出现的次数存储在哈希表中。然后计算数组 nums3 和 nums4 所有可能的元素之和，并在哈希表中查找是否存在和它们互为相反数的元素。如果存在，说明这些组合的总和为 0。

创建哈希表：用于存储 nums1 和 nums2 所有可能的元素之和及其出现次数。

计算并存储和：遍历 nums1 和 nums2，计算所有可能的和，并在哈希表中记录每个和出现的次数。

查找和计算次数：遍历 nums3 和 nums4，计算所有可能的和，然后在哈希表中查找是否有互为相反数的和。如果有，将它们出现的次数累加到结果中。

返回结果：返回所有满足条件的组合次数。

时间复杂度：O(n^2)。其中 n 是数组的长度。

哈希表解题代码如下

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        Map<Integer, Integer> map = new HashMap<>();
        int count = 0;

        // 计算 nums1 和 nums2 所有可能的元素之和
        for (int a : nums1) {
            for (int b : nums2) {
                map.put(a + b, map.getOrDefault(a + b, 0) + 1);
            }
        }

        // 查找 nums3 和 nums4 的和的相反数是否在哈希表中
        for (int c : nums3) {
            for (int d : nums4) {
                count += map.getOrDefault(-(c + d), 0);
            }
        }

        return count;
    }
}

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

# 9. 三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

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

示例 1：

输入：nums = [-1,0,1,2,-1,-4]

输出：[[-1,-1,2],[-1,0,1]]

解释：

nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。

nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。

nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。

不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。

注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1]

输出：[]

解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0,0,0]

输出：[[0,0,0]]

解释：唯一可能的三元组和为 0 。

提示：

3 <= nums.length <= 3000
-105 <= nums[i] <= 105

解题思路如下：力扣链接 (opens new window)

这道题的难点是不能包含重复的答案，对于[0,0,0,0,0]这个数组，答案只有一个[0,0,0]。首先我们对数组先排序一次，在排好序的数组上，就很容判断前后元素是否相等，这样可以过滤掉重复的答案。

因此这道题目使用哈希法并不十分合适，因为在去重的操作中有很多细节需要注意，在面试中很难直接写出没有bug的代码。接下来我来介绍另一个解法：双指针法，这道题目使用双指针法要比哈希法高效一些

首先对数组进行排序。

然后遍历排序后的数组：
如果当前元素大于0，因为之后的元素都会更大，所以直接结束循环。

如果当前元素和前一个元素相同，则跳过当前元素，这样做的目的是避免重复选择相同的起点元素a，从而生成重复的三元组。

对每个不同的元素a，在其右侧数组中使用双指针法寻找两个数b和c：
初始化左指针left为当前元素的下一个位置，右指针right为数组的最右端。

当left小于right时，计算a + b + c的和。
如果和大于0，右指针左移。

如果和小于0，左指针右移。

如果和为0，记录这一组解，并对左右指针进行去重处理，然后左指针右移，右指针左移。

返回所有找到的三元组。

时间复杂度：O(n^2)。排序操作的时间复杂度为 O(nlogn)，之后的遍历操作和双指针搜索的总时间复杂度为 O(n^2)

双指针解题代码如下

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums); // 对数组进行排序

        // 遍历数组，寻找a + b + c = 0的组合
        for (int i = 0; i < nums.length; i++) {
            // 如果第一个元素大于0，则后面的元素加起来也不可能等于0
            if (nums[i] > 0) {
                return result;
            }

            // 去重：跳过连续重复的元素
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            // 使用双指针寻找b和c
            int left = i + 1; // 左指针
            int right = nums.length - 1; // 右指针
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right]; // 计算三数之和
                if (sum > 0) {
                    right--; // 总和大于0，右指针左移
                } else if (sum < 0) {
                    left++; // 总和小于0，左指针右移
                } else {
                    // 找到了一组解，加入结果列表
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    // 去重：避免左右指针指向重复元素
                    while (left < right && nums[right] == nums[right - 1]) right--;
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    // 移动左右指针，寻找下一组解
		    left++;
                    right--;                    
                }
            }
        }
        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

# 10. 四数之和

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案。

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0

输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：

输入：nums = [2,2,2,2,2], target = 8

输出：[[2,2,2,2]]

提示：

1 <= nums.length <= 200
-109 <= nums[i] <= 109
-109 <= target <= 109

解题思路如下：力扣链接 (opens new window)

四数之和，和三数之和是一个思路，都是使用双指针法结合排序，然后找到数组nums中所有和为target的四元组。

初始化结果列表：List<List<Integer>> result用于存储所有符合条件的四元组。

对数组排序：Arrays.sort(nums)对数组进行排序，以便使用双指针法。

外层遍历：外层循环从0到nums.length,遍历数组中的每个元素作为四元组的第一个元素,循环变量为i
剪枝操作：如果nums[i]大于0且大于target，则后续的四元组之和不可能等于target（因为排序后的数组是非递减的），可以直接返回结果。

去重：如果当前元素与前一个元素相同，则跳过当前循环，以避免重复的四元组。

内层遍历：第二层循环从i + 1开始，遍历数组中的每个元素作为四元组的第二个元素。循环变量为j。
去重：类似于外层循环的去重操作，避免第二个元素重复。

双指针查找：定义两个指针left和right，分别指向剩余部分的起始和末尾。
查找和为target的组合：在循环内，根据四数之和与target的比较结果移动left和right。
如果四数之和大于target，将right左移。

如果四数之和小于target，将left右移。

如果找到和为target的组合，将其添加到结果列表中。

返回结果：最终返回存储所有符合条件的四元组的result列表。

时间复杂度是由排序操作和双层循环组成的，可以表示为O(n log n) + O(n^2) * O(n)。但是，由于n^2在数量级上远大于n log n，因此总体时间复杂度可以近似为O(n^3)。

双指针解题代码如下

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);  // 对数组进行排序
        
        for (int i = 0; i < nums.length; i++) {  // 外层循环，固定第一个数
            if (nums[i] > 0 && nums[i] > target) {  // 剪枝操作
                return result;
            }
            if (i > 0 && nums[i - 1] == nums[i]) {  // 去重
                continue;
            }
            
            for (int j = i + 1; j < nums.length; j++) {  // 内层循环，固定第二个数
                // j > i + 1 确保了j不是在它的初始位置
                // 如果j在初始位置，那么它前面没有元素可以用来比较是否重复
                if (j > i + 1 && nums[j - 1] == nums[j]) {  // 去重
                    continue;
                }

                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--;  // 和大于target，右指针左移
                    } else if (sum < target) {
                        left++;  // 和小于target，左指针右移
                    } else {
                        result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));  // 添加结果
                        // 对左右指针去重
                        while (left < right && nums[right] == nums[right - 1]) right--;
                        while (left < right && nums[left] == nums[left + 1]) left++;

                        left++;  // 移动指针以寻找新的组合
                        right--;
                    }
                }
            }
        }
        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
43

编辑此页

上次更新: 2025/01/02, 01:21:04

← 链表系列字符串系列→