1、四数相加
不需要考虑去重
四个数组采两个数组一起相加的遍历方式，为了缩短时间复杂度。
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4)
{
unordered_map <int,int> map;
for(int a : nums1)
{
for(int b: nums2)
{
map[a+b]++;
}
}
int count = 0;
for (int c: nums3)
{
for (int d : nums4)
{
if(map.find(0-(c+d)) != map.end())
{
count += map[0-(c+d)];
}
}
}
return count;
}
};
其中的 0-（c+d) 相当于map中的键值value
2、赎金信
数组类型的哈希表
class Solution {
public:
bool canConstruct(string ransomNote, string magazine)
{
int record[26] = {0};
if(ransomNote.size() > magazine.size())
{
return false;
}
for (int i = 0; i < magazine.length(); i++)
{
record[magazine[i] - 'a']++;
}
for (int j = 0; j < ransomNote.length();j++)
{
record[ransomNote[j] - 'a']--;
if(record[ransomNote[j] - 'a'] < 0)
{
return false;
}
}
return true;
}
};
length() 和 size() 的主要区别在于它们被设计用于不同类型的对象：length() 通常用于字符串，而 size() 用于集合。
length() 方法常用于获取字符串中字符的数量。
size() 方法通常用于获取集合（如列表、集合、映射等）中元素的数量。
3、三数之和
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums)
{
vector<vector<int>> result;
sort(nums.begin(), nums.end());
for(int i = 0; i < nums.size(); i++)
{
if(nums[i] > 0)
{
return result;
}
//去重
if(i > 0 && nums[i] == nums[i - 1])
{
continue;
}
int left = i + 1;
int right = nums.size() - 1;
while(right > left)
{
if(nums[i] + nums[left] + nums[right] > 0) right--;
else if (nums[i] + nums[left] + nums[right] < 0) left ++;
else
{
result.push_back(vector<int>{nums[i],nums[left],nums[right]});
while(right > left && nums[right] == nums[right - 1]) right--;
while(right > left && nums[left] == nums[left + 1]) left++;
}
//添加新解到 result 之后，可以立即更新 left 和 right 指针
//（即 left++ 和 right--），以避免在 while 循环条件中重复检查这些条件。
right--;
left++;
}
}
return result;
}
};
初始化结果向量：首先，函数初始化一个空的二维向量 result，用于存储满足条件的三元组。
每个三元组本身是一个包含三个整数的向量，因此我们需要一个容器来存储所有这些三元组。
排序数组：然后，sort对输入的整数数组 nums 进行排序。排序是解决问题的关键步骤，因为它允许我们使用双指针技术来高效地查找和为零的三元组。
遍历数组：接下来，使用一个 for 循环遍历排序后的数组 nums。循环变量 i 从 0 开始，表示三元组中的第一个数。
剪枝操作：
如果 nums[i] 大于 0，由于数组已排序，那么后续的所有元素都将大于 0，因此不可能再找到和为零的三元组，直接返回结果。
如果当前元素与前一个元素相同（即 i > 0 && nums[i] == nums[i - 1]），则跳过当前循环迭代，以避免重复的三元组。
双指针法：
在遍历过程中，对于每个 i，使用两个指针 left 和 right 分别指向 i 的下一个位置和数组的末尾。
进入一个 while 循环，只要 right 大于 left，就执行以下操作：
计算三数之和（nums[i] + nums[left] + nums[right]）。
如果和大于 0，说明 right 指向的元素太大，将 right 向左移动一位。
如果和小于 0，说明 left 指向的元素太小，将 left 向右移动一位。
如果和等于 0，找到了一个满足条件的三元组，将其添加到 result 中。
去重操作（针对 b 和 c）：
在找到一个满足条件的三元组后，为了避免添加重复的三元组，需要跳过 left 和 right 指针上所有与当前元素相同的元素。这是通过两个嵌套的 while 循环实现的。
然后，将 right 和 left 指针分别向内移动一位，以继续寻找其他可能的三元组。
返回结果：遍历完成后，返回包含所有满足条件的三元组的 result 向量。
4、四数之和
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> result;
sort(nums.begin(), nums.end());
for (int k = 0; k < nums.size(); k++) {
// 剪枝处理
if (nums[k] > target && nums[k] >= 0) {
break; // 这里使用break，统一通过最后的return返回
}
// 对nums[k]去重
if (k > 0 && nums[k] == nums[k - 1]) {
continue;
}
for (int i = k + 1; i < nums.size(); i++) {
// 2级剪枝处理
if (nums[k] + nums[i] > target && nums[k] + nums[i] >= 0) {
break;
}
// 对nums[i]去重
if (i > k + 1 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = nums.size() - 1;
while (right > left) {
// nums[k] + nums[i] + nums[left] + nums[right] > target 会溢出
if ((long) nums[k] + nums[i] + nums[left] + nums[right] > target) {
right--;
// nums[k] + nums[i] + nums[left] + nums[right] < target 会溢出
} else if ((long) nums[k] + nums[i] + nums[left] + nums[right] < target) {
left++;
} else {
result.push_back(vector<int>{nums[k], nums[i], nums[left], nums[right]});
// 对nums[left]和nums[right]去重
while (right > left && nums[right] == nums[right - 1]) right--;
while (right > left && nums[left] == nums[left + 1]) left++;
// 找到答案时，双指针同时收缩
right--;
left++;
}
}
}
}
return result;
}
};