代码随想录打卡

女爷i 2024-02-22 09:14 44阅读 0赞

## 前言 ##

代码随想录算法训练营day07

--------------------

## 一、Leetcode 454.四数相加II ##

### 1.题目 ###

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

css

复制代码

`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

提示：

ini

复制代码

`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`

来源：力扣（LeetCode） 链接：[leetcode.cn/problems/4s…][leetcode.cn_problems_4s]

### 2.解题思路 ###

方法一：分组 + 哈希表

我们可以将四个数组分成两部分，AA 和 BB 为一组，CC 和 DD 为另外一组。

对于 AA 和 BB，我们使用二重循环对它们进行遍历，得到所有 A\[i\]+B\[j\]A\[i\]+B\[j\] 的值并存入哈希映射中。对于哈希映射中的每个键值对，每个键表示一种 A\[i\]+B\[j\]A\[i\]+B\[j\]，对应的值为 A\[i\]+B\[j\]A\[i\]+B\[j\] 出现的次数。

对于 CC 和 DD，我们同样使用二重循环对它们进行遍历。当遍历到 C\[k\]+D\[l\]C\[k\]+D\[l\] 时，如果 −(C\[k\]+D\[l\])−(C\[k\]+D\[l\]) 出现在哈希映射中，那么将 −(C\[k\]+D\[l\])−(C\[k\]+D\[l\]) 对应的值累加进答案中。

最终即可得到满足 A\[i\]+B\[j\]+C\[k\]+D\[l\]=0A\[i\]+B\[j\]+C\[k\]+D\[l\]=0 的四元组数目。

### 3.代码实现 ###

*  方法一 ：hashmap统计

java

复制代码

`class Solution { public int fourSumCount(int[] A, int[] B, int[] C, int[] D) { Map<Integer, Integer> countAB = new HashMap<Integer, Integer>(); for (int u : A) { for (int v : B) { countAB.put(u + v, countAB.getOrDefault(u + v, 0) + 1); } } int ans = 0; for (int u : C) { for (int v : D) { if (countAB.containsKey(-u - v)) { ans += countAB.get(-u - v); } } } return ans; } }`

## 二、Leetcode 383. 赎金信 ##

### 1.题目 ###

给你两个字符串：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

提示：

matlab

复制代码

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

### 2.解题思路 ###

方法一：字符统计

题目要求使用字符串 magazinemagazine 中的字符来构建新的字符串 ransomNoteransomNote，且ransomNoteransomNote 中的每个字符只能使用一次，只需要满足字符串 magazinemagazine 中的每个英文字母 (’a’-’z’)(’a’-’z’) 的统计次数都大于等于 ransomNoteransomNote 中相同字母的统计次数即可。

*  如果字符串 magazinemagazine 的长度小于字符串 ransomNoteransomNote 的长度，则我们可以肯定 magazinemagazine 无法构成 ransomNoteransomNote，此时直接返回 falsefalse。
 *  首先统计 magazinemagazine 中每个英文字母 aa 的次数 cnt\[a\]cnt\[a\]，再遍历统计 ransomNoteransomNote 中每个英文字母的次数，如果发现 ransomNoteransomNote 中存在某个英文字母 cc 的统计次数大于 magazinemagazine 中该字母统计次数 cnt\[c\]cnt\[c\]，则此时我们直接返回 falsefalse。

### 3.代码实现 ###

java

复制代码

`class Solution { public boolean canConstruct(String ransomNote, String magazine) { if (ransomNote.length() > magazine.length()) { return false; } int[] cnt = new int[26]; for (char c : magazine.toCharArray()) { cnt[c - 'a']++; } for (char c : ransomNote.toCharArray()) { cnt[c - 'a']--; if(cnt[c - 'a'] < 0) { return false; } } return true; } }`

## 三、Leetcode15. 三数之和 ##

### 1.题目 ###

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

链接：[leetcode.cn/problems/3s…][leetcode.cn_problems_3s]

### 2.解题思路 ###

方法一 ：排序 + 双指针

### 3.代码实现 ###

java

复制代码

`class Solution { public List<List<Integer>> threeSum(int[] nums) { int n = nums.length; Arrays.sort(nums); List<List<Integer>> ans = new ArrayList<List<Integer>>(); // 枚举 a for (int first = 0; first < n; ++first) { // 需要和上一次枚举的数不相同 if (first > 0 && nums[first] == nums[first - 1]) { continue; } // c 对应的指针初始指向数组的最右端 int third = n - 1; int target = -nums[first]; // 枚举 b for (int second = first + 1; second < n; ++second) { // 需要和上一次枚举的数不相同 if (second > first + 1 && nums[second] == nums[second - 1]) { continue; } // 需要保证 b 的指针在 c 的指针的左侧 while (second < third && nums[second] + nums[third] > target) { --third; } // 如果指针重合，随着 b 后续的增加 // 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环 if (second == third) { break; } if (nums[second] + nums[third] == target) { List<Integer> list = new ArrayList<Integer>(); list.add(nums[first]); list.add(nums[second]); list.add(nums[third]); ans.add(list); } } } return ans; } }`

作者：东离与糖宝  
链接：https://juejin.cn/post/7232229178278723641  
来源：稀土掘金  
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

[leetcode.cn_problems_4s]: https://link.juejin.cn?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2F4sum-ii
[leetcode.cn_problems_3s]: https://link.juejin.cn?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2F3sum