本期，我给大家讲述的是关于 n数之和这类题目的讲解，我会给大家讲解两数之和，三数之和和四数之和这三道题目。
（一）两数之和
链接如下：两数之和
题目如下：
题意分析：
要解决查找两个数字之和的问题，可以通过遍历数组并检查每个可能的数字对来使用暴力方法。然而，这种方法的时间复杂度为 O（n^2），效率不高。
💨 解决方法：
- 更好的方法是使用哈希表将数组的值存储为键，将其索引存储为值；
- 然后，对于数组中的每个数字，可以检查哈希表中是否存在目标总和与当前数字之间的差异；
- 如果存在，那么表示就已经找到了加起来等于目标总和的数字对。这种方法的时间复杂度为 O（n），效率更高。
具体步奏：
step 1：构建一个哈希表，用于记录各值和值对应的下标；
step 2：检查哈希表中是否存在目标总和与当前数字之间的差异：
- 如果存在说明我们先前遍历的时候它出现过，根据记录的下标，我们返回两个数字的索引，就可以得到结果；
- 如果没有，我们将当前数字及其索引添加到哈希表中
代码展示：
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { int size = nums.size(); vector <int> res; if (!size) return res; // 定义哈希表 unordered_map<int, int> tmp; for (int i = 0; i < size; i ++) { if (tmp.find(target - nums[i]) != tmp.end()) { // find函数返回tmp.end()代表未找到，否则代表找到 // 将结果存入数组 res.push_back(tmp[target - nums[i]]); res.push_back(i); break; } else { tmp[nums[i]] = i; // 将未找到的值插入哈希表中，继续遍历 } } return res; } };
性能分析：
- 时间复杂度：O(n)，仅仅遍历数组一次，每次查询哈希表都是O(1)
- 空间复杂度：O(n)，最坏情况下找到数组结尾才找到，其他都加入哈希表，因此哈希表最长为n−1的长度
（二）三数之和
链接如下：三数之和
题目如下：
题意分析：
- 本题跟上述两数之和的题目类似。为了解决“三数之和”问题，我们可以使用两指针方法；
- 首先，我们按非降序对输入数组进行排序。然后，我们使用 for 循环遍历数组，对于每个元素，我们使用两个指针来查找另外两个元素，它们的总和为当前元素的负数；
- 如果我们找到这样的三元组，我们将其添加到我们的结果向量中。为了避免重复，我们跳过任何重复的元素。
具体步奏：
step 1：我们对这个无序的数组进行排序操作，使用sort函数优先对其排序；
step 2：紧接着遍历该数组，对于三个数字都要判断是否相邻有重复的情况，因此要对其进行去重操作；
step 3：对于每个遍历到的元素假设它是三元组中最小的一个，那么另外两个一定在后面；
step 4：接下来，使用双指针的思想遍历去数组，因为最后得到的和为0，找到两个位置处的元素之和等于开始定义的最小值的相反值；
step 5：如果二者相加大于目标值，说明右指针太大了，那就将其左移缩小，相反如果二者相加小于目标值，说明左指针太小了，将其右移扩大，直到两指针相遇为止。
代码展示：
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 (i > 0 && nums[i] == nums[i-1]) continue; //如果当前元素不是重复的,将目标值设置为当前元素的负值 int target = -nums[i]; //然后，将两个指针（左和右）分别初始化到向量中的下一个元素和最后一个元素。 int left = i+1, right = nums.size()-1; //只要左小于右，该循环就会继续 while (left < right) { //检查左右值的总和是否等于目标值 if (nums[left] + nums[right] == target) { //如果是,将三个值的向量添加到结果向量中 result.push_back({nums[i], nums[left], nums[right]}); //然后，向左递增，向右递减。 left++; right--; while (left < right && nums[left] == nums[left-1]) left++; while (left < right && nums[right] == nums[right+1]) right--; } //如果左侧和右侧的值之和小于目标值，则函数向左递增 else if (nums[left] + nums[right] < target) { left++; } //如果它大于目标值，则函数向右递减 else { right--; } } } //最后，该函数返回包含所有唯一三元组的结果向量，这些三元组的总和为零 return result; } };
性能分析：
- 时间复杂度：O（n^2），其中 n 是输入数组的长度。此实现使用两个嵌套循环遍历所有可能的数字对，并使用哈希表来检查数组中是否存在完成三元组所需的第三个数字，所以时间复杂度为O（n^2）；
- 空间复杂度：O(N)。
（三）四数之和
链接如下： 四数之和
题目如下：
题意分析：
同“三数之和”一样，如果通过遍历数组并检查每个可能的数字这种暴力方法，那么时间时间复杂度将达到O(N^4）。因此，还是跟上述一样整体思路是使用嵌套循环和两个指针来循环访问数组并查找四个元素。
题意涉及在数组中查找所有唯一的“四胞胎”，这些四胞胎的总和等于给定的目标值。
具体步奏：
step 1：我们对这个无序的数组进行排序操作，使用sort函数优先对其排序；
step 2：注意这里因为是四个数，因此需要注意区间的变化情况；
step 3：紧接着遍历该数组，对于四个数字都要判断是否相邻有重复的情况，因此要对其进行去重操作；
step 4：接下来，使用双指针的思想遍历去数组，如果最后得到的和等于target，记录下来，但是四者中间的数字相加可能还会有；
step 5：如果四者相加大于目标值，说明右指针太大了，那就将其左移缩小，相反如果四者相加小于目标值，说明左指针太小了，将其右移扩大，直到两指针相遇为止。
代码展示：
class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { vector<vector<int>> res; if (nums.empty()) return res; //首先按升序对输入数组进行排序，这允许在迭代过程中有效地跳过重复值 sort(nums.begin(), nums.end()); int n = nums.size(); //外部循环遍历四个数中的前三个整数 for (int i = 0; i < n - 3; i++) { if (i > 0 && nums[i] == nums[i - 1]) continue; //内部循环访问第四个整数 for (int j = i + 1; j < n - 2; j++) { //去重 if (j > i + 1 && nums[j] == nums[j - 1]) continue; //双指针用于查找总和为目标值的其余两个整数 int left = j + 1, right = n - 1; while (left < right) { //检查总和是否等于目标值 long sum =(long) 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++; left++; while (left < right && nums[right] == nums[right - 1]) right--; right--; } //和小于目标值，则函左指针向右 else if (sum < target) { left++; } //如果它大于目标值，则右指针向左 else { right--; } } } } return res; } };
性能分析：
- 时间复杂度：O(N^3），其中 n 是数组的长度。排序的时间复杂度是 O(nlogn)，枚举四元组的时间复杂度是 O(N^3），所以时间复杂度为 O(N^3）
- 空间复杂度： O(N)，排序修改了输入数组 nums，实际情况中不一定允许这样的情况发生，因此也可以看成使用了一个额外的数组存储了数组 nums 的副本并排序，空间复杂度为O(N)。
总体而言，由于嵌套循环，代码的时间复杂度为 O（n^3），但排序步骤降低了常数因子并提高了整体性能。
到此，便是以上题目的全部讲解。希望对大家有所帮助，感谢大家的阅读！！！
