自律是普通人最大的武器系列专栏直达链接 Linux进入专栏 → C语言进入专栏 → C进入专栏 → MySQL进入专栏 → 算法刷题进入专栏 → 博客主页虚无的纽扣 作者仓库github | gitee引言最近因为一些原因拖更了很长时间的算法文章后续我会慢慢补回来今天要讲解的是三数之和、四数之和。三数之和原题15. 三数之和 - 力扣LeetCode。接下来我们先来解析一下这个题目该题目的要求是要求我们找到三个数并且这三个数的和为零通过题目要求我们可以发现一个三元组除了在全零的情况下一定至少要存在一个数为负数不然相加无法得到零并且该数组为递增数组。根据这个发现接下来我们来讲解这道题的解题思路。首先根据我们上面的发现我们可以先将下标为0的数固定下来记作con然后让left等于1right等于n-1当它们三个相加之和大于0时right就减减当相加之和小于0时left就加加。而当它们三个的和等于0时就记录下结果并且很明显如果left或right下一次移动时的数和当前数字一样那么结果还是0就没必要重复计算所以我们直接进行判断并且跳过所有的重复数字直接进行运算就可以节省一点时间。当left大于或等于right后第一次循环结束将让con加加进行第二轮循环直到con对应的位置大于零为止。通过上面的讲解相信大家应该大致理解了一点思路接下来贴出源代码结合着思路和代码很容易就能理解这道题class Solution { public: vectorvectorint threeSum(vectorint nums) { sort(nums.begin(), nums.end()); int con 0; vectorvectorint ve; while (nums.size() - con 2 nums[con] 0) { int left con 1, right nums.size() - 1; while (left right) { if (nums[left] nums[right] nums[con] 0) { right--; } else if (nums[left] nums[right] nums[con] 0) { left; } else { ve.push_back({nums[left], nums[right--], nums[con]}); while (left right nums[left] nums[left - 1]) left; while (left right nums[right] nums[right 1]) right--; } } con; while (con nums.size() nums[con] nums[con - 1]) { con; } } return ve; } };四数之和原题18. 四数之和 - 力扣LeetCode。四数之和是三数之和的超级加强版写起来特别的恶心和复杂题目解析就不做了和上面的三数之和差不多我们直接进入解析首先该数组并不是有序的我们先用排序将它变成有序然后我们还是一样先把数组前面的数固定不一样的是这次要固定两个并且如果数组的最小值加数组最大的三个值就已经大于目标值就代表该数组无论如何都找不到结果直接返回空。我们要写一个深度超级深的大循环第一层循环跟三数之和一样固定最小值设为i如果i、i1、i2、i3的值加起来已经大于目标值则说明不管怎么移动都会比目标值大没有意义直接break。而如果i、n-1、n-2、n-3的值加起来小于目标值也没有意义不管怎么移动都不可能大于或等于目标值所以直接进入下一轮循环。固定下来i值后我们再固定下来j值等于i1接着重复上一级循环的两个判断如果都通过了就设left和right接下来的写法就不用我说了直接用三数之和的解法来写就行。需要注意的是因为数据过多可能会导致四数之和超出int的范围所以最好将记录结果的值设为long或者long long类型在进行计算时最好也进行一次强转。这题究极臃肿究极复杂究极恶心并没有任何价值大家大概理解就行下附源代码class Solution { public: vectorvectorint fourSum(vectorint nums, int target) { vectorvectorint quadruplets; if (nums.size() 4) { return quadruplets; } sort(nums.begin(), nums.end()); int length nums.size(); for (int i 0; i length - 3; i) { if (i 0 nums[i] nums[i - 1]) { continue; } if ((long) nums[i] nums[i 1] nums[i 2] nums[i 3] target) { break; } if ((long) nums[i] nums[length - 3] nums[length - 2] nums[length - 1] target) { continue; } for (int j i 1; j length - 2; j) { if (j i 1 nums[j] nums[j - 1]) { continue; } if ((long) nums[i] nums[j] nums[j 1] nums[j 2] target) { break; } if ((long) nums[i] nums[j] nums[length - 2] nums[length - 1] target) { continue; } int left j 1, right length - 1; while (left right) { long sum (long) nums[i] nums[j] nums[left] nums[right]; if (sum target) { quadruplets.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 quadruplets; } };