题目链接：https://leetcode.cn/problems/4sum-ii/description/
给你四个整数数组
nums1、nums2、nums3和nums4，数组长度都是n，请你计算有多少个元组(i, j, k, l)能满足：
0 <= i, j, k, l < nnums1[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.lengthn == nums2.lengthn == nums3.lengthn == nums4.length1 <= n <= 200-228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228
这道题目也是哈希法的经典运用，和之前我们做过的242.有效的字母异位词思路一致，先遍历一个集合，然后再去另一个集合中找符合的元素，这道题目有四个数组，我们需要两两数组结合成一个集合，然后最后合并之后也就只剩下两个集合了，操作就和之前一致了。
然后哈希法的结构我们需要选择map来解决，因为我们需要存储元素是否出现过（这里是两个数组合并之后的元素），以及出现过的次数，第一个map存两个数组元素之和a+b，和出现的次数，然后在第二个map找0-(c+d) 是否在map中出现过，如果出现过就用count（用来统计 a+b+c+d = 0 出现的次数）把map中key对应的value也就是出现次数统计出来，最后返回统计值 count 即可。
（1）Python版本代码
class Solution:
def fourSumCount(self, nums1, nums2, nums3, nums4):
hashmap = {} # key: nums1[i] + nums2[j], value: count
for i in range(len(nums1)):
for j in range(len(nums2)): # 计算nums1[i] + nums2[j]的和，存入hashmap
if nums1[i] + nums2[j] in hashmap:
hashmap[nums1[i] + nums2[j]] += 1
else: # 如果不存在，初始化为1
hashmap[nums1[i] + nums2[j]] = 1
count = 0 # 计数器
for i in range(len(nums3)):
for j in range(len(nums4)): # 计算nums3[i] + nums4[j]的和，如果存在hashmap中，count加上对应的value
if -(nums3[i] + nums4[j]) in hashmap:
count += hashmap[-nums3[i] - nums4[j]]
return count
if __name__ == "__main__":
nums1 = list(map(int, input().split()))
nums2 = list(map(int, input().split()))
nums3 = list(map(int, input().split()))
nums4 = list(map(int, input().split()))
solution = Solution()
print(solution.fourSumCount(nums1, nums2, nums3, nums4))
（2）C++版本代码
#include <iostream>
#include <vector>
#include <unordered_map>
#include <sstream>
class Solution {
public:
int fourSumCount(std::vector<int>& nums1, std::vector<int>& nums2, std::vector<int>& nums3, std::vector<int>& nums4) {
std::unordered_map<int, int> hashmap; // key: nums1[i] + nums2[j] 的和, value: 出现次数
// 计算 nums1[i] + nums2[j] 的和，并存储在 hashmap 中
for (int i : nums1) {
for (int j : nums2) {
hashmap[i + j]++;
}
}
int count = 0; // 计数器
// 计算 nums3[i] + nums4[j] 的和，并在 hashmap 中查找是否有对应的负数
for (int i : nums3) {
for (int j : nums4) {
if (hashmap.find(-i - j) != hashmap.end()) {
count += hashmap[-i - j];
}
}
}
return count;
}
};
std::vector<int> readVector() {
std::string line;
std::getline(std::cin, line);
std::istringstream stream(line);
std::vector<int> nums;
int number;
while (stream >> number) {
nums.push_back(number);
}
return nums;
}
int main() {
Solution solution;
std::cout << "输入四个整数数组，每个数组一行，数字之间用空格分隔：" << std::endl;
std::vector<int> nums1 = readVector();
std::vector<int> nums2 = readVector();
std::vector<int> nums3 = readVector();
std::vector<int> nums4 = readVector();
std::cout << "结果：" << solution.fourSumCount(nums1, nums2, nums3, nums4) << std::endl;
return 0;
}
题目链接：https://leetcode.cn/problems/ransom-note/description/
给你两个字符串：
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 <= 105ransomNote和magazine由小写英文字母组成
这道题目也和前面的242.有效的字母异位词解决思路基本一致，这几题都有异曲同工之妙。
（1）Python版本代码
数组
class Solution:
def canConstruct(self, ransomNote, magazine):
# 创建一个长度为26的数组来存储每个字母在杂志字符串中出现的次数
# 每个字母对应数组的一个位置，例如 'a' 对应位置 0，'b' 对应位置 1，以此类推
count = [0] * 26
# 遍历杂志字符串，更新数组中各字母出现的次数
for char in magazine:
count[ord(char) - ord('a')] += 1
# 遍历赎金信字符串
for char in ransomNote:
# 检查当前字母是否足够
if count[ord(char) - ord('a')] == 0:
return False
count[ord(char) - ord('a')] -= 1
return True
if __name__ == '__main__':
s = Solution()
ransomNote = input()
magazine = input()
print(s.canConstruct(ransomNote, magazine))
map
class Solution:
def canConstruct(self, ransomNote, magazine):
dic = {} # 创建一个字典，用于存储杂志字符串中每个字符出现的次数
# 遍历杂志字符串，统计每个字符出现的次数
for i in magazine:
if i in dic: # 如果字符已经在字典中，则增加其计数
dic[i] += 1
else: # 如果字符不在字典中，则将其添加到字典中，并初始化计数为1
dic[i] = 1
# 遍历赎金信字符串，检查每个字符是否能从杂志字符串中找到
for i in ransomNote:
if i in dic and dic[i] > 0: # 如果字符在杂志字符串中，并且数量大于0
dic[i] -= 1 # 使用一个字符，相应减少字典中该字符的计数
else: # 如果字符不在杂志字符串中，或者数量不足
return False # 无法构建赎金信，返回False
# 如果所有赎金信的字符都能在杂志字符串中找到且数量足够，则返回True
return True
if __name__ == '__main__':
s = Solution()
ransomNote = input()
magazine = input()
print(s.canConstruct(ransomNote, magazine))
magazine 的长度， N 是赎金信字符串 ransomNote 的长度。两者相比较就可以发现这题更适合使用数组来实现哈希法，因为题目限制了数组的大小，因此使用数组空间复杂度会很低。
这道题目python还有一种更加简洁的写法，但是不推荐大家写，因为面试大概率不会让你这样去写的。
class Solution:
def canConstruct(self, ransomNote, magazine):
for i in ransomNote:
if ransomNote.count(i) > magazine.count(i):
return False
return True
（2）C++版本代码
数组
#include <iostream>
#include <string>
#include <vector>
class Solution {
public:
bool canConstruct(std::string ransomNote, std::string magazine) {
std::vector<int> count(26, 0);
// 统计杂志中各字母出现的次数
for (char ch : magazine) {
count[ch - 'a']++;
}
// 检查赎金信中的字符是否可以由杂志中的字符组成
for (char ch : ransomNote) {
if (--count[ch - 'a'] < 0) {
return false;
}
}
return true;
}
};
int main() {
Solution solution;
std::string ransomNote, magazine;
std::getline(std::cin, ransomNote);
std::getline(std::cin, magazine);
std::cout << (solution.canConstruct(ransomNote, magazine) ? "True" : "False") << std::endl;
return 0;
}
map
#include <iostream>
#include <string>
#include <unordered_map>
class Solution {
public:
bool canConstruct(std::string ransomNote, std::string magazine) {
std::unordered_map<char, int> charCount;
// 统计杂志中各字母出现的次数
for (char ch : magazine) {
charCount[ch]++;
}
// 检查赎金信中的字符是否可以由杂志中的字符组成
for (char ch : ransomNote) {
if (--charCount[ch] < 0) {
return false;
}
}
return true;
}
};
int main() {
Solution solution;
std::string ransomNote, magazine;
std::getline(std::cin, ransomNote);
std::getline(std::cin, magazine);
std::cout << (solution.canConstruct(ransomNote, magazine) ? "True" : "False") << std::endl;
return 0;
}
题目链接：https://leetcode.cn/problems/3sum/description/
给你一个整数数组
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
这道题目强烈推荐大家去看看卡哥的视频讲解，很详细，然后再去看看代码随想录文字版讲解。
这道题目可以使用哈希法，也可以使用双指针法，关键就在于去重，因为题目要求答案中不可以包含重复的三元组，但是哈希法相对于双指针法更加的麻烦，麻烦就在去重的操作上面，有很多的小细节需要注意。
我们在使用双指针法之前必须要先对数组进行排序（这是使用双指针法的前提，这也是为啥前面两数之和我们不能使用双指针法的原因），然后我们在查找的过程中，根据三数之和与0的比较结果，决定是移动左指针还是右指针，如果和小于0，移动左指针；如果和大于0，移动右指针，在移动指针时，我们还要确保指针不会越界。
下面是去重操作需要注意的方面：
（1）Python版本代码
class Solution:
def threeSum(self, nums):
# 对数组进行排序
nums.sort()
n = len(nums)
res = []
# 遍历数组，固定第一个数
for i in range(n):
# 如果当前数字大于0，则三数之和一定大于0，结束循环
if nums[i] > 0:
break
# 跳过重复数字
if i > 0 and nums[i] == nums[i - 1]:
continue
# 左右指针初始化
left, right = i + 1, n - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
# 如果三数之和为0，加入到结果中
if total == 0:
res.append([nums[i], nums[left], nums[right]])
# 跳过重复数字
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
# 移动指针
left += 1
right -= 1
# 如果三数之和小于0，移动左指针
elif total < 0:
left += 1
# 如果三数之和大于0，移动右指针
else:
right -= 1
return res
if __name__ == "__main__":
solution = Solution()
nums = list(map(int, input().split()))
print(solution.threeSum(nums))
为什么跳过重复数字要用nums[i] == nums[i - 1]而不能用nums[i] == nums[i + 1]？
当使用 nums[i] == nums[i - 1]：
相反如果使用 nums[i] == nums[i + 1]：
[1, 1, 1, 2, 2] 中寻找三数之和为6的组合，我们会在第一个1的时候就跳过后面所有的1，从而错过有效的组合 (1, 2, 3)。（2）C++版本代码
#include <iostream>
#include <vector>
#include <algorithm>
class Solution {
public:
std::vector<std::vector<int>> threeSum(std::vector<int>& nums) {
std::sort(nums.begin(), nums.end());
std::vector<std::vector<int>> res;
int n = nums.size();
// 遍历数组，固定第一个数
for (int i = 0; i < n; ++i) {
// 如果当前数字大于0，则三数之和一定大于0，结束循环
if (nums[i] > 0) break;
// 跳过重复数字
if (i > 0 && nums[i] == nums[i - 1]) continue;
// 左右指针初始化
int left = i + 1, right = n - 1;
while (left < right) {
int total = nums[i] + nums[left] + nums[right];
// 如果三数之和为0，加入到结果中
if (total == 0) {
res.push_back({nums[i], nums[left], nums[right]});
// 跳过重复数字
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
// 移动指针
left++;
right--;
}
// 如果三数之和小于0，移动左指针
else if (total < 0) {
left++;
}
// 如果三数之和大于0，移动右指针
else {
right--;
}
}
}
return res;
}
};
int main() {
Solution solution;
std::vector<int> nums;
int num;
while (std::cin >> num) {
nums.push_back(num);
if (std::cin.peek() == '\n') break;
}
std::vector<std::vector<int>> result = solution.threeSum(nums);
for (const auto& triple : result) {
for (int num : triple) {
std::cout << num << " ";
}
std::cout << std::endl;
}
return 0;
}
题目链接：https://leetcode.cn/problems/4sum/description/
给你一个由
n个整数组成的数组nums，和一个目标值target。请你找出并返回满足下述全部条件且不重复的四元组[nums[a], nums[b], nums[c], nums[d]]（若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < na、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
这题跟上一题思路大致一样，需要再加上一层for循环，然后去重的操作需要注意一下，和上一题相比有所区别，三数之和是使用一个外层循环遍历数组，对于每个元素，使用双指针在剩余部分寻找两个数，使得三数之和为0，而四数之和使用两层循环固定前两个数，然后在剩余的数组中使用双指针寻找另外两个数，使得四数之和达到目标值，前面是固定找相加等于0，后面是用户自己输入的target，因此后续去重操作有所不同，四数之和在去重方面相比三数之和更加复杂，因为它涉及到两层循环的去重，而三数之和只需要处理外层循环和双指针的去重，本题虽然看起来和前面做的454.四数相加Ⅱ但本质还是有所不同，前者是四个数组，本题只有一个数组，需要考虑去重操作。
（1）Python版本代码
class Solution:
def fourSum(self, nums, target):
nums.sort() # 对数组进行排序
n = len(nums) # 数组长度
res = [] # 用于存储结果的列表
# 遍历数组，固定第一个数
for i in range(n):
# 如果当前数字大于目标值且当前数字和目标值都大于0，则后续不可能找到符合条件的组合
if nums[i] > target and nums[i] > 0 and target > 0:
break
# 跳过重复数字
if i > 0 and nums[i] == nums[i - 1]:
continue
# 第二层循环，固定第二个数
for j in range(i + 1, n):
# 如果两个固定数字之和已大于目标值且目标值大于0，则后续不可能找到符合条件的组合
if nums[i] + nums[j] > target and target > 0:
break
# 跳过重复数字
if j > i + 1 and nums[j] == nums[j - 1]:
continue
# 双指针寻找剩余两个数
left, right = j + 1, n - 1
while left < right:
sum = nums[i] + nums[j] + nums[left] + nums[right] # 四数之和
if sum == target: # 如果和等于目标值，添加到结果中
res.append([nums[i], nums[j], nums[left], nums[right]])
# 跳过重复数字
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
elif sum < target: # 如果和小于目标值，移动左指针
left += 1
else: # 如果和大于目标值，移动右指针
right -= 1
return res
if __name__ == "__main__":
solution = Solution()
nums = list(map(int, input().split()))
target = int(input())
print(solution.fourSum(nums, target))
（2）C++版本代码
#include <iostream>
#include <vector>
#include <algorithm>
class Solution {
public:
std::vector<std::vector<int>> fourSum(std::vector<int>& nums, int target) {
std::sort(nums.begin(), nums.end()); // 对数组进行排序
int n = nums.size();
std::vector<std::vector<int>> res;
// 遍历数组，固定第一个数
for (int i = 0; i < n; ++i) {
// 如果当前数字大于目标值且当前数字和目标值都大于0，则后续不可能找到符合条件的组合
if (nums[i] > target && nums[i] > 0 && target > 0) break;
// 跳过重复数字
if (i > 0 && nums[i] == nums[i - 1]) continue;
// 第二层循环，固定第二个数
for (int j = i + 1; j < n; ++j) {
// 如果两个固定数字之和已大于目标值且目标值大于0，则后续不可能找到符合条件的组合
if (nums[i] + nums[j] > target && target > 0) break;
// 跳过重复数字
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
// 双指针寻找剩余两个数
int left = j + 1, right = n - 1;
while (left < right) {
int sum = nums[i] + nums[j] + nums[left] + nums[right]; // 四数之和
if (sum == target) { // 如果和等于目标值，添加到结果中
res.push_back({nums[i], nums[j], nums[left], nums[right]});
// 跳过重复数字
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
} else if (sum < target) { // 如果和小于目标值，移动左指针
left++;
} else { // 如果和大于目标值，移动右指针
right--;
}
}
}
}
return res;
}
};
int main() {
Solution solution;
int target;
std::vector<int> nums;
int num;
std::cout << "输入数组元素，以空格分隔：" << std::endl;
while (std::cin >> num) {
nums.push_back(num);
if (std::cin.peek() == '\n') break;
}
std::cout << "输入目标值：" << std::endl;
std::cin >> target;
std::vector<std::vector<int>> result = solution.fourSum(nums, target);
for (const auto& quad : result) {
for (int num : quad) {
std::cout << num << " ";
}
std::cout << std::endl;
}
return 0;
}