leetcode--hash表2

349.两个数组的交集

给定两个数组 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

原理

本质上是hash数组

创建辅助数组 ans 和 res：

ans 用于记录 nums1 中每个元素是否出现过。数组大小为 1001，是因为题目中规定 nums1[i] 和 nums2[i] 的值都在 [0, 1000] 范围内。
res 用于存储交集元素。假设两个数组的交集最大长度为 1000，因此这里预留了 1001 个位置来存储交集的元素。

处理 nums1 数组：

遍历 nums1 数组，将每个元素标记为出现过。使用 ans[nums1[i]]++ 来标记。每次遇到某个元素时，若它尚未在 ans 中出现过，就将其标记为 1。

处理 nums2 数组：

遍历 nums2 数组，对于每个元素，如果它在 ans 数组中已经被标记过（即 ans[nums2[i]] != 0），则说明它出现在 nums1 中，因此它是交集的一部分，将它加入到 res 数组中。
处理重复元素时，使用 ans[nums2[i]]-- 来确保同一个交集元素只添加一次。每次添加后，通过减少 ans[nums2[i]] 来标记已经处理过该元素，避免重复添加。

截取最终交集数组：

最后，通过 Arrays.copyOf(res, count) 截取 res 数组中有效的部分，即去除多余的元素。

返回交集数组：

最终返回 res1，它包含了 nums1 和 nums2 的交集元素。

时间复杂度分析：

遍历 nums1 数组：
时间复杂度为 O(m)，其中 m 是 nums1 的长度。

遍历 nums2 数组：
时间复杂度为 O(n)，其中 n 是 nums2 的长度。

数组复制：
通过 Arrays.copyOf(res, count) 将结果数组从 res 截取成实际交集的大小，时间复杂度为 O(k)，其中 k 是交集元素的个数。

因此，总时间复杂度为 O(m + n)，即两个数组的长度之和。

空间复杂度分析：

辅助数组 ans 和 res：

ans 和 res 数组的大小都是 1001，空间复杂度为 O(1)，即常数空间，因为数组大小是固定的，不会随输入规模变化。

最终结果数组 res1：

结果数组的大小是交集元素的个数，最坏情况下空间复杂度是 O(min(m, n))。

因此，总空间复杂度为 O(min(m, n))。

代码

class Solution {public int[] intersection(int[] nums1, int[] nums2) {// 初始化一个大小为1001的数组用于存储nums1的元素出现情况，最大值为1000int[] ans = new int[1001];// 用于存储交集结果的数组int[] res = new int[1001];// 记录交集数组中的元素个数int count = 0;// 遍历nums1数组，将每个元素标记为出现过for (int i = 0; i < nums1.length; i++) {if (ans[nums1[i]] == 0) {  // 如果该元素在nums1中第一次出现ans[nums1[i]]++;  // 标记该元素}}// 遍历nums2数组，找到nums1中也存在的元素for (int i = 0; i < nums2.length; i++) {if (ans[nums2[i]] != 0) {  // 如果该元素在nums1中出现过res[count++] = nums2[i];  // 将该元素放入结果数组ans[nums2[i]]--;  // 处理重复的元素，避免再次加入}}// 将结果数组截取为实际交集的长度，并返回int[] res1 = Arrays.copyOf(res, count);return res1;}
}

350.两个数组的交集II

给你两个整数数组 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

进阶：

如果给定的数组已经排好序呢？你将如何优化你的算法？
如果 nums1 的大小比 nums2 小，哪种方法更优？
如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？

原理

创建辅助数组 ans 和 res：

ans 用于记录 nums1 中每个元素出现的次数。ans[nums1[i]] 记录了 nums1 中元素 nums1[i] 的出现次数。
res 用于存储交集结果。我们预留了 1001 个位置来存储交集的元素，足够存储 nums1 和 nums2 中的元素。

统计 nums1 中元素的出现次数：

遍历 nums1 数组，利用 ans[nums1[i]]++ 统计每个元素在 nums1 中的出现次数。
这样，ans 数组中存储了每个 nums1 元素的出现次数。

遍历 nums2 查找交集：

遍历 nums2 数组，对每个元素 nums2[i]，检查其是否在 nums1 中出现（即检查 ans[nums2[i]] != 0）。
如果该元素在 nums1 中存在且 ans[nums2[i]] 大于 0，表示该元素是交集的一部分：
将该元素加入 res 数组。
更新 ans[nums2[i]]--，表示该元素在 nums1 中的出现次数减少，避免重复添加。

返回交集结果：

最终，使用 Arrays.copyOf(res, count) 截取有效的交集部分，并返回交集数组。

关键点：

交集中的每个元素出现的次数等于该元素在两个数组中出现次数的最小值。这是通过 ans[nums2[i]]-- 实现的：每次添加一个交集元素后，都会减少该元素在 nums1 中的出现次数，避免重复添加。

时间复杂度分析：

遍历 nums1 数组：
时间复杂度为 O(m)，其中 m 是 nums1 的长度。遍历数组并更新 ans 数组的每个元素。

遍历 nums2 数组：
时间复杂度为 O(n)，其中 n 是 nums2 的长度。遍历 nums2 数组并检查每个元素是否在 nums1 中出现。

数组复制：
通过 Arrays.copyOf(res, count) 截取结果数组的有效部分，时间复杂度为 O(k)，其中 k 是交集元素的个数。

因此，总时间复杂度为 O(m + n)，即两个数组的长度之和。

空间复杂度分析：

辅助数组 ans 和 res：

ans 数组大小为 1001，res 数组的大小也为 1001。空间复杂度是 O(1)，即常数空间，因为这两个数组的大小是固定的。

最终结果数组 res1：

结果数组的大小是交集元素的个数，最坏情况下空间复杂度为 O(min(m, n))。

因此，总空间复杂度为 O(min(m, n))。

代码

class Solution {public int[] intersect(int[] nums1, int[] nums2) {// 用于记录nums1中每个元素的出现次数int[] ans = new int[1001];  // 假设元素值的范围是 [0, 1000]，所以数组大小为1001// 用于存储交集结果int[] res = new int[1001];  // 预留一个最大容量的数组存储交集int count = 0;  // 记录交集数组中的元素个数// 遍历nums1数组，将每个元素的出现次数记录到ans数组中for (int i = 0; i < nums1.length; i++) {// 如果该元素未在ans数组中出现过，则将其出现次数增加if (ans[nums1[i]] >= 0) {ans[nums1[i]]++;}}// 遍历nums2数组，查找在nums1中也出现的元素，并按次数存入结果数组for (int i = 0; i < nums2.length; i++) {// 如果nums2中的元素在nums1中出现过且出现次数大于0if (ans[nums2[i]] != 0) {res[count++] = nums2[i];  // 将该元素加入交集ans[nums2[i]]--;  // 减少该元素在nums1中的出现次数}}// 截取有效交集元素部分int[] res1 = Arrays.copyOf(res, count);return res1;  // 返回交集结果}
}

202.快乐数

编写一个算法来判断一个数 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

原理

判断一个数是否是快乐数：

快乐数的关键在于反复计算一个数的各个数字的平方和，直到：
结果变为 1，那么这个数是快乐数；
如果过程进入无限循环，则不是快乐数。
我们使用一个 HashMap 来记录数的出现，若某个数已经出现过，说明它进入了循环，直接返回 false。

算法步骤：

初始化：
创建一个 HashMap<Integer, Integer> 来记录计算过程中出现的每个数。
如果一开始输入的 n 就是 1，直接返回 true，因为 1 是快乐数。
计算平方和：
定义 happyNumber(int num) 方法，该方法计算并返回一个数 num 的各个数字的平方和。例如，num = 82 时，计算 8^2 + 2^2 = 64 + 4 = 68。
判断无限循环：
通过 HashMap 判断某个数是否已经出现过，若某个数已经出现，则表示它进入了循环，直接返回 false。
若计算结果为 1，则说明该数是快乐数，返回 true。

注意：

如果数在计算过程中一直重复，并没有变为 1，说明这个数陷入了一个循环，这时候直接返回 false。
效率优化： 使用 HashMap 来记录已经出现的数，避免重复计算，减少计算量。

时间复杂度：

每次计算一个数的平方和的时间复杂度是 O(log n)，因为我们需要遍历该数的所有位（与该数的位数相关）。
在最坏的情况下，重复计算可能会遍历所有数字，直到检测出一个循环或得到 1。根据历史经验，快乐数的数值通常不会增长到非常大的数字，最多只需要做 O(1) 次迭代。
因此，总时间复杂度为 O(log n)，其中 n 是输入的数字。

空间复杂度：

需要一个 HashMap 来存储所有已出现的数字。最坏情况下，当 n 变成一个很大的数时，可能需要记录多个中间值，因此空间复杂度是 O(log n)，因为这与 n 的位数有关。

代码

class Solution {// 主函数，判断 n 是否是快乐数public boolean isHappy(int n) {// 创建一个哈希表，用于记录出现过的数HashMap<Integer, Integer> happy = new HashMap<>();// 如果 n 等于 1，直接返回 true，1 是快乐数if (n == 1) {return true;}// 将 n 放入哈希表中，标记该数已经出现过happy.put(n, 1);// 通过不断替换 n，直到达到 1 或者出现无限循环while (!happy.containsKey(happyNumber(n))) {// 计算 n 的平方和并赋值给 ansint ans = happyNumber(n);// 如果平方和为 1，返回 true，表示 n 是快乐数if (ans == 1) {return true;}// 将新的数 ans 放入哈希表中，表示它已经出现过happy.put(ans, 1);// 更新 n 为 ans，继续计算n = ans;}// 如果进入无限循环，返回 false，表示 n 不是快乐数return false;}// 辅助函数，计算一个数的各个位上数字的平方和public int happyNumber(int num) {int sum = 0;// 遍历 num 的每一位while (num > 0) {// 取出当前最低位int digit = num % 10;// 将当前最低位的平方加到 sumsum += (digit * digit);// 去掉当前最低位num /= 10;}// 返回数字各位平方和的结果return sum;}
}

1.两数之和

给定一个整数数组 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]

原理

问题描述： 给定一个整数数组 nums 和一个目标值 target，你需要在数组中找到和为目标值的两个数，并返回它们的下标。假设每个输入只对应一个答案，且不能使用相同的元素两次。

算法思路：

这是一个典型的“两数之和”问题。我们可以通过使用哈希表（HashMap）来高效地找到答案。
对于每个数字 nums[i]，我们可以计算出目标值 target 减去该数字的差值，即 target - nums[i]。这个差值就是我们在之前遍历过的数组中的一个数（如果存在的话），我们只需判断哈希表中是否包含这个差值。如果包含，说明找到了两个数的和为 target，然后直接返回这两个数的下标。

算法步骤：

初始化一个哈希表 mapSum，它的键是数组中的元素值，值是该元素在数组中的索引。
遍历 nums 数组，对于每一个元素 nums[i]，计算出它的“补数” target - nums[i]。
如果该补数已经在哈希表中，则说明找到了两个数之和等于 target，将这两个数的索引返回。
如果补数不存在于哈希表中，则将当前数字 nums[i] 及其索引 i 存入哈希表。
由于题目保证每种输入只会对应一个答案，算法会在找到答案后立即返回，不会继续遍历。

时间复杂度：

哈希表的查找、插入操作的平均时间复杂度是 O(1)。
遍历 nums 数组一次，时间复杂度是 O(n)，其中 n 是 nums 数组的长度。
因此，总时间复杂度为 O(n)。

空间复杂度：

需要一个哈希表来存储数组中的每个元素及其索引，最坏情况下，哈希表的大小为 n，因此空间复杂度为 O(n)。

代码

class Solution {public int[] twoSum(int[] nums, int target) {// 创建一个哈希表，用于存储每个数及其对应的索引HashMap<Integer, Integer> mapSum = new HashMap<>();// 初始化返回结果数组，保存找到的两个索引int[] ans = new int[2];// 遍历 nums 数组，查找目标值for (int i = 0; i < nums.length; i++) {// 判断当前元素的 complement（即目标值减去当前元素）是否已经存在于 map 中if (mapSum.containsKey(target - nums[i])) {// 如果存在，说明当前元素与 map 中的某个元素和为 target// 获取那个元素的索引并保存到答案数组中ans[0] = mapSum.get(target - nums[i]);ans[1] = i;// 返回答案return ans;}// 如果没有找到，保存当前元素及其索引到 map 中mapSum.put(nums[i], i);}// 如果没有找到符合条件的两个数，返回默认的空数组（根据题意，保证总有解，所以实际不会走到这里）return ans;}
}

454.四数相加II

给你四个整数数组 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
解释：
两个元组如下：
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (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

原理

问题描述： 给定四个整数数组 nums1, nums2, nums3 和 nums4，每个数组的长度为 n，我们要找到所有满足以下条件的元组 (i, j, k, l)：

nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0。
输出这些满足条件的元组个数。

算法思路：

该问题可以通过哈希表来优化，通过将 nums1 和 nums2 的所有两数组和存入哈希表，然后在 nums3 和 nums4 中查找其负和来减少时间复杂度。

具体步骤：

第一步： 遍历数组 nums1 和 nums2，计算它们的所有两数组和 nums1[i] + nums2[j]，将这些和存储在哈希表 mapSum 中，同时记录每个和出现的次数。这一步的时间复杂度是 O(n²)，其中 n 是数组的长度。

第二步： 再次遍历 nums3 和 nums4，计算它们的和 nums3[i] + nums4[j]，并查找这个和的负值 -(nums3[i] + nums4[j]) 是否存在于 mapSum 中。如果存在，就说明 nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0，此时就增加计数。

最终结果： 最后返回计数器 count，它存储了所有符合条件的四元组个数。

时间复杂度：

第一层循环遍历 nums1 和 nums2，计算所有两数组和，时间复杂度是 O(n²)。
第二层循环遍历 nums3 和 nums4，查找其负和是否在 mapSum 中，时间复杂度也是 O(n²)。
因此，总时间复杂度为 O(n²)，其中 n 是每个数组的长度。

空间复杂度：

我们使用了一个哈希表 mapSum 来存储 nums1 + nums2 的所有组合及其出现次数。最坏情况下，哈希表的大小是 O(n²)，因此 空间复杂度为 O(n²)。

代码

class Solution {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {// 初始化计数器 count 和输入数组的长度 lenint count = 0;int len = nums1.length;// 创建哈希表 mapSum，用于存储 nums1 + nums2 的所有和及其出现次数HashMap<Integer, Integer> mapSum = new HashMap<>();// 第一层循环遍历 nums1 和 nums2 的所有组合，计算 nums1[i] + nums2[j] 的和并存储在 mapSum 中for (int i = 0; i < len; i++) {for (int j = 0; j < len; j++) {int sum = nums1[i] + nums2[j];// 如果 sum 还没在 mapSum 中出现过，初始化为 1if (!mapSum.containsKey(sum)) {mapSum.put(sum, 1);} else {// 如果 sum 已经出现过，增加计数mapSum.put(sum, mapSum.get(sum) + 1);}}}// 第二层循环遍历 nums3 和 nums4 的所有组合，计算 nums3[i] + nums4[j] 的和并检查其负值是否存在于 mapSum 中for (int i = 0; i < len; i++) {for (int j = 0; j < len; j++) {int target = -(nums3[i] + nums4[j]);// 如果 target 在 mapSum 中出现过，说明找到了符合条件的四元组，增加计数if (mapSum.containsKey(target)) {count += mapSum.get(target);}}}// 返回符合条件的四元组个数return count;}
}

但这个代码耗时并不短，可以看一下这道题的最优解法，看不懂也没事，上面能看懂就行

原理

问题描述： 给定四个整数数组 nums1, nums2, nums3 和 nums4，数组长度为 n，我们要找到所有符合条件的四元组 (i, j, k, l)，使得：
nums1[i]+nums2[j]+nums3[k]+nums4[l]=0nums1[i] + nums2[j] + nums3[k] + nums4[l] = 0nums1[i]+nums2[j]+nums3[k]+nums4[l]=0
返回满足条件的四元组的个数。

算法思路： 传统的暴力解法会遍历 nums1, nums2, nums3, 和 nums4 的每一种组合，时间复杂度为 O(n^4)，这对于较大的输入规模来说效率太低。通过优化，可以利用哈希表或计数数组来减少时间复杂度。

具体步骤：

计算每个数组的最小值和最大值： 先分别计算每个数组 nums1, nums2, nums3, nums4 的最大值和最小值。这些值用于计算可能的和的范围。

初始化一个记录数组： 根据 nums1 和 nums2 数组的所有组合，计算它们的和，并将其频次记录到一个数组 record 中。由于和的范围可能较大，因此我们通过偏移来确保和的值都能放入 record 数组的合法索引位置。

偏移的原因：由于和可能是负数，因此我们将 record 数组的索引范围调整为 [min, max] 之间，避免出现负数索引。

查找和的负值： 遍历 nums3 和 nums4 的所有组合，计算其和的负值。如果负值在 record 数组中存在，说明找到了一个符合条件的四元组，累加计数。

时间复杂度：

计算最小值和最大值：遍历每个数组一次，时间复杂度是 O(n)。
填充记录数组：对 nums1 和 nums2 的每一对组合进行遍历，时间复杂度是 O(n²)。
查找匹配的和：对 nums3 和 nums4 的每一对组合进行遍历，时间复杂度是 O(n²)。
总时间复杂度：O(n²)，因为暴力的 O(n⁴) 方法被优化为 O(n²)。

空间复杂度：

使用一个大小为 max - min + 1 的数组 record 来存储和的频率。最坏情况下，这个数组的大小是 O(n²)，因此空间复杂度是 O(n²)。

代码

class Solution {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {// 计算nums1的最大值和最小值int max1 = Integer.MIN_VALUE, min1 = Integer.MAX_VALUE;for (int i1 : nums1) {if (i1 > max1) {max1 = i1;}if (i1 < min1) {min1 = i1;}}int[] minMaxNums1 = new int[] { min1, max1 }; // 存储nums1的最小值和最大值// 计算nums2的最大值和最小值int max2 = Integer.MIN_VALUE, min2 = Integer.MAX_VALUE;for (int i2 : nums2) {if (i2 > max2) {max2 = i2;}if (i2 < min2) {min2 = i2;}}int[] minMaxNums2 = new int[] { min2, max2 }; // 存储nums2的最小值和最大值// 计算nums3的最大值和最小值int max3 = Integer.MIN_VALUE, min3 = Integer.MAX_VALUE;for (int i3 : nums3) {if (i3 > max3) {max3 = i3;}if (i3 < min3) {min3 = i3;}}int[] minMaxNums3 = new int[] { min3, max3 }; // 存储nums3的最小值和最大值// 计算nums4的最大值和最小值int max4 = Integer.MIN_VALUE, min4 = Integer.MAX_VALUE;for (int i4 : nums4) {if (i4 > max4) {max4 = i4;}if (i4 < min4) {min4 = i4;}}int[] minMaxNums4 = new int[] { min4, max4 }; // 存储nums4的最小值和最大值// 计算可能的和的最大值和最小值// max表示所有可能的和的最大值，min表示所有可能的和的最小值int max = Math.max(minMaxNums1[1] + minMaxNums2[1], -minMaxNums3[0] - minMaxNums4[0]);int min = Math.min(minMaxNums1[0] + minMaxNums2[0], -minMaxNums3[1] - minMaxNums4[1]);// 初始化一个记录和频率的数组int result = 0;int[] record = new int[max - min + 1];// 遍历nums1和nums2的所有组合，并将其和存入record数组for (int i : nums1)for (int j : nums2) {record[i + j - min]++; // 将和偏移到record数组的正确位置}// 遍历nums3和nums4的所有组合，查找其负和是否出现在record数组中for (int i : nums3)for (int j : nums4) {result = result + record[-i - j - min]; // 如果找到匹配的和，累加到结果中}// 返回结果return result;}
}

383.赎金信

给你两个字符串：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 由小写英文字母组成

原理

这个问题的目标是判断能否从 magazine 字符串中提取出 ransomNote 字符串所需要的字符。我们需要确保在 magazine 中每个字符的数量足够支撑 ransomNote 中每个字符的需求。算法的核心思想是基于频率计数，具体步骤如下：

频率统计：

我们首先用一个长度为26的数组 mapM 来记录 magazine 字符串中每个字符的出现次数。这里使用一个数组是因为题目中只涉及小写字母（即26个字母）。
对于 magazine 中的每个字符，更新 mapM 数组中对应的索引值（mapM[i] 对应字符 i + 'a'）。

验证是否能构成：

遍历 ransomNote 字符串，检查其中的每个字符是否能在 magazine 中找到足够的字符。
每找到一个字符，减少 mapM 数组中对应字符的计数。如果 mapM[ransomNote.charAt(i) - 'a'] 的值变成负数，说明 magazine 中没有足够的该字符，返回 false。

最终检查：

完成对 ransomNote 的字符遍历后，我们再次检查 mapM 中所有的值，确保没有负数。如果有负数，表示 magazine 中某个字符的数量不足以构成 ransomNote，因此返回 false。
如果 mapM 中所有的值都大于等于零，说明 ransomNote 可以由 magazine 中的字符构成，返回 true。

时间复杂度：

遍历 magazine 字符串来统计字符频率：O(m)，其中 m 是 magazine 的长度。
遍历 ransomNote 字符串来检查字符需求：O(n)，其中 n 是 ransomNote 的长度。
最后遍历 mapM 数组来检查每个字符的计数：O(26)，常数时间。

所以，总的时间复杂度是 O(m + n)，其中 m 和 n 分别是 magazine 和 ransomNote 的长度。

空间复杂度：

我们使用了一个长度为26的整数数组 mapM 来记录字符频率，因此空间复杂度是 O(1)，因为这个数组的大小是固定的（只有26个字符）。

代码

class Solution {public boolean canConstruct(String ransomNote, String magazine) {// 定义一个长度为26的数组mapM，用于记录magazine中每个字母的出现次数int[] mapM = new int[26];// 遍历magazine字符串，统计每个字母的出现频率for (int i = 0; i < magazine.length(); i++) {mapM[magazine.charAt(i) - 'a']++; // 将字符的ASCII值减去'a'得到对应的索引，进行计数}// 遍历ransomNote字符串，检查每个字母是否在magazine中有足够的字符for (int i = 0; i < ransomNote.length(); i++) {mapM[ransomNote.charAt(i) - 'a']--; // 找到ransomNote中的字符，并减少对应的计数}// 遍历mapM数组，检查是否有任何字母的计数小于0// 如果有小于0的值，表示ransomNote中的某个字母在magazine中不足够的次数for (int i = 0; i < 26; i++) {if (mapM[i] < 0) {return false; // 若有字母的出现次数不足，返回false}}// 如果遍历完所有字母后，所有字母的计数都大于或等于0，说明ransomNote可以由magazine构成return true;}
}

15.三数之和

给你一个整数数组 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

原理

这个问题要求我们找到所有满足条件的三元组 nums[i] + nums[j] + nums[k] == 0，其中 i < j < k。为了高效地解决这个问题，我们采用了双指针法，结合排序来优化查找过程，并且使用哈希表避免重复三元组。下面是详细的步骤和原理：

排序数组：

首先对数组 nums 进行排序。排序的目的是利用排序后的数组可以通过双指针技术来高效地找到满足条件的三元组。

遍历数组的第一个数：

外层循环遍历数组中的每个元素，假设当前元素 nums[i] 是三元组中的第一个数。我们在遍历时，跳过相同的数字，以避免重复三元组。例如，如果当前数字和前一个数字相同，跳过本次循环。

判断是否满足条件：

如果 nums[i] > 0，我们可以提前终止循环，因为数组已经排序，接下来的数字都比 nums[i] 大，不可能找到和为0的三元组。

双指针法：

对于每个 nums[i]，使用两个指针 left 和 right，分别指向 i+1 和数组的末尾。
然后计算 nums[i] + nums[left] + nums[right] 的和：
如果和小于0，说明需要增大和，因此左指针右移。
如果和大于0，说明需要减小和，因此右指针左移。
如果和等于0，说明找到一个满足条件的三元组，将其加入结果列表，并且调整指针。

避免重复三元组：

在找到一个符合条件的三元组后，我们需要确保不加入重复的三元组。为此，我们使用 mapSum 哈希表记录已经找到的三元组。如果一个三元组已经存在于 mapSum 中，就跳过当前的三元组。

返回结果：

最后返回存储所有符合条件的三元组的 ans 列表。

时间复杂度：

排序： 排序数组需要 O(n log n)，其中 n 是数组的长度。
双指针遍历： 对于每个元素，使用双指针进行扫描，时间复杂度是 O(n)。
因此，整个算法的时间复杂度是 O(n^2)，其中 n 是数组的长度。

空间复杂度：

使用一个 ans 列表来存储符合条件的三元组，空间复杂度是 O(k)，其中 k 是结果中的三元组个数。
使用一个哈希表 mapSum 来避免重复三元组，空间复杂度是 O(k)。
总的空间复杂度是 O(k)，其中 k 是符合条件的三元组的数量。

代码

class Solution {public List<List<Integer>> threeSum(int[] nums) {// 创建一个列表来存储符合条件的三元组List<List<Integer>> ans = new ArrayList<>();// 使用HashMap来记录已经出现过的三元组，避免重复结果HashMap<List<Integer>, Integer> mapSum = new HashMap<>();// 对数组进行排序，便于使用双指针技术Arrays.sort(nums);// 遍历数组中的每个元素（作为三元组中的第一个数）for (int i = 0; i < nums.length - 2; i++) {// 如果当前数和前一个数相同，则跳过，避免重复三元组if (i > 0 && nums[i] == nums[i - 1]) {continue;}// 如果当前数大于0，说明之后的数都大于0，不可能找到和为0的三元组，提前终止if (nums[i] > 0) {break;}// 使用双指针，left指向i+1，right指向数组末尾int left = i + 1;int right = nums.length - 1;// 双指针搜索合适的两个数，使得nums[i] + nums[left] + nums[right] == 0while (left < right) {// 计算当前三元组的和int sum = nums[i] + nums[left] + nums[right];// 如果和小于0，说明需要增大sum，左指针右移if (sum < 0) {left++;}// 如果和大于0，说明需要减小sum，右指针左移else if (sum > 0) {right--;}// 如果和等于0，找到了一个三元组else {List<Integer> temp = new ArrayList<>();temp.add(nums[i]);temp.add(nums[left]);temp.add(nums[right]);// 如果当前三元组没有出现过，则加入结果集if (!mapSum.containsKey(temp)) {ans.add(temp);mapSum.put(temp, 1);}// 左右指针都需要移动，避免重复三元组left++;right--;}}}// 返回所有符合条件的三元组return ans;}
}

但是耗时很长，最优解重写了部分东西。

18.四数之和

给你一个由 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

原理

这段代码的目的是解决“四数之和”问题，即在给定的整数数组 nums 中找出所有不重复的四元组，使得四元组的和等于给定的目标值 target。该问题通常通过使用双指针和排序来优化。

1. 数组排序：

为了方便处理，首先对数组进行排序。排序使得我们可以使用双指针技巧来减少不必要的搜索空间，并有效地跳过重复的元素。

2. 使用 HashSet 去重：

为了避免重复的四元组，使用 HashSet 来存储符合条件的四元组。由于 HashSet 会自动去重，只有不重复的四元组会被添加进去。

3. 双层循环遍历选择前两个数：

通过两层循环，分别遍历数组中的前两个数 nums[i] 和 nums[j]，选择它们作为四元组的前两个元素。
如果当前的元素和前一个元素相同，跳过当前元素，避免重复的四元组（例如：选择了重复的 nums[i] 或 nums[j]）。

4. 双指针查找后两个数：

对于每对 (nums[i], nums[j])，使用双指针 left 和 right 来查找满足条件的后两个数。
初始化时，left 指向 nums[j+1]，right 指向数组的最后一个元素。
计算当前四个数的和 sum = nums[i] + nums[j] + nums[left] + nums[right]。
如果 sum 等于目标值 target，则找到一个符合条件的四元组，将其加入 HashSet 中。
如果 sum 大于目标值，说明需要减小和，右指针左移。
如果 sum 小于目标值，说明需要增大和，左指针右移。

5. 跳过重复元素：

在移动指针时，要跳过重复的元素，避免重复的三元组或四元组。使用 while 循环来跳过相同的元素。

6. 结果返回：

最终，HashSet 中存储的所有四元组被转换为 ArrayList 并返回。

时间复杂度：

排序的时间复杂度是 O(n log n)。
两层循环分别遍历 i 和 j，每一层的循环的时间复杂度为 O(n)。在每次循环中，双指针操作的时间复杂度是 O(n)，因此总体的时间复杂度是 O(n^3)。

空间复杂度：

空间复杂度是 O(k)，其中 k 是符合条件的四元组的个数。主要的空间消耗来自 HashSet 中存储的结果。

代码

class Solution {// 使用一个HashSet来存储符合条件的四元组，去重重复的结果public List<List<Integer>> fourSum(int[] nums, int target) {// 用于存储结果的集合，HashSet自动去重Set<List<Integer>> ans = new HashSet<>();// 对数组进行排序，便于后续使用双指针技巧Arrays.sort(nums);// 获取数组的长度int len = nums.length;// 如果数组长度小于4，直接返回空的列表if (len < 4) {return new ArrayList<>(ans);}// 如果数组长度恰好为4，直接计算四个元素之和if (len == 4) {if ((long) target != (long) ((long) nums[0] + (long) nums[1] + (long) nums[2] + (long) nums[3]))) {return new ArrayList<>(ans);  // 如果四个数的和不等于target，返回空列表} else {ans.add(Arrays.asList(nums[0], nums[1], nums[2], nums[3]));  // 否则，返回这一个四元组return new ArrayList<>(ans);}}// 遍历数组，选择四元组的第一个数for (int i = 0; i < len - 3; i++) {// 如果当前元素和前一个元素相同，跳过，避免重复的四元组if (i > 0 && nums[i] == nums[i - 1]) {continue;}// 遍历数组，选择四元组的第二个数for (int j = i + 1; j < len - 2; j++) {// 如果当前元素和前一个元素相同，跳过，避免重复的四元组if (j > i + 1 && nums[j] == nums[j - 1]) {continue;}// 初始化左右指针，进行双指针搜索int left = j + 1;int right = len - 1;// 使用双指针查找和为target的三元组while (left < right) {// 计算当前四个数的和int sum = nums[i] + nums[j] + nums[left] + nums[right];if (sum == target) {  // 如果和为target，找到一个符合条件的四元组ans.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));}// 如果当前和大于目标值，右指针左移if (sum > target) {right--;// 跳过重复元素while (nums[right] == nums[right + 1] && left < right) {right--;}} else {  // 如果当前和小于目标值，左指针右移left++;// 跳过重复元素while (nums[left] == nums[left - 1] && left < right) {left++;}}}}}// 将结果转换为列表返回return new ArrayList<>(ans);}
}