双指针（典型算法思想）——OJ例题算法解析思路
目录
一、283. 移动零 - 力扣（LeetCode）
1. 问题分析
2. 算法思路
3. 代码逐行解析
4. 示例运行
5. 时间复杂度与空间复杂度
6. 总结
二、1089. 复写零 - 力扣（LeetCode）
1. 问题分析
2. 算法思路
3. 代码逐行解析
4. 示例运行
5. 时间复杂度与空间复杂度
6. 总结
三、202. 快乐数 - 力扣（LeetCode）
1. 问题分析
2. 算法思路
3. 代码逐行解析
4. 示例运行
5. 时间复杂度与空间复杂度
6. 总结
四、11. 盛最多水的容器 - 力扣（LeetCode）
1. 问题分析
2. 算法思路
3. 代码逐行解析
4. 示例运行
5. 时间复杂度与空间复杂度
6. 总结
五、611. 有效三角形的个数 - 力扣（LeetCode）
1. 问题分析
2. 算法思路
3. 代码逐行解析
4. 示例运行
5. 时间复杂度与空间复杂度
6. 总结
六、 LCR 179. 查找总价格为目标值的两个商品 - 力扣（LeetCode）
1. 问题分析
2. 算法思路
3. 代码逐行解析
4. 示例运行
5. 时间复杂度与空间复杂度
6. 总结
七、15. 三数之和 - 力扣（LeetCode）
1. 问题分析
2. 算法思路
3. 代码逐行解析
4. 示例运行
5. 时间复杂度与空间复杂度
6. 总结
八、18. 四数之和 - 力扣（LeetCode）
1. 问题分析
2. 算法思路
3. 代码逐行解析
4. 示例运行
5. 时间复杂度与空间复杂度
6. 总结
一、283. 移动零 - 力扣（LeetCode）
1. 问题分析
目标：将数组中的所有
0移动到末尾，同时保持非零元素的相对顺序。示例：
输入：
[0, 1, 0, 3, 12]输出：
[1, 3, 12, 0, 0]2. 算法思路
核心思想：使用双指针技术，一个指针（
cur）用于遍历数组，另一个指针（dest）用于指向当前可以放置非零元素的位置。具体步骤：
初始化
dest = -1，表示当前还没有非零元素。遍历数组，用
cur指针检查每个元素：
如果当前元素
nums[cur]是非零值：
将
dest向右移动一位（dest++），表示有一个新的非零元素可以放置。将
nums[cur]和nums[dest]交换，将非零值放到dest的位置。移动
cur指针继续遍历。如果当前元素
nums[cur]是0：
直接移动
cur指针，跳过0。遍历结束后，所有非零元素都被移动到数组的前面，而
0被留在了后面。3. 代码逐行解析
class Solution { public:void moveZeroes(vector<int>& nums) {int cur = 0, dest = -1; // 初始化 cur 和 destwhile (cur < nums.size()) { // 遍历数组if (nums[cur]) { // 如果当前元素是非零值dest++; // dest 向右移动swap(nums[cur], nums[dest]); // 将非零值交换到 dest 的位置cur++; // 移动 cur 指针} else { // 如果当前元素是 0cur++; // 直接移动 cur 指针}}} };
cur指针：用于遍历数组，检查每个元素。dest指针：指向当前可以放置非零元素的位置。swap(nums[cur], nums[dest])：将非零值交换到dest的位置，确保非零值的相对顺序不变。4. 示例运行
以输入
[0, 1, 0, 3, 12]为例：
初始状态：
cur = 0,dest = -1，数组为[0, 1, 0, 3, 12]。
cur = 0，nums[0] = 0，跳过，cur++。
cur = 1，nums[1] = 1，dest++（dest = 0），交换nums[1]和nums[0]，数组变为[1, 0, 0, 3, 12]，cur++。
cur = 2，nums[2] = 0，跳过，cur++。
cur = 3，nums[3] = 3，dest++（dest = 1），交换nums[3]和nums[1]，数组变为[1, 3, 0, 0, 12]，cur++。
cur = 4，nums[4] = 12，dest++（dest = 2），交换nums[4]和nums[2]，数组变为[1, 3, 12, 0, 0]，cur++。遍历结束，结果为
[1, 3, 12, 0, 0]。5. 时间复杂度与空间复杂度
时间复杂度：O(n)，其中
n是数组的长度。每个元素最多被遍历一次。空间复杂度：O(1)，只使用了常数级别的额外空间。
6. 总结
这段代码通过双指针技术，高效地将数组中的
0移动到末尾，同时保持了非零元素的相对顺序。其核心思想是利用dest指针记录非零元素的位置，并通过交换操作将非零值逐步移动到数组的前面。
二、1089. 复写零 - 力扣（LeetCode）
1. 问题分析
目标：在数组中复制每个
0，并将后续元素向右移动。如果数组空间不足，则丢弃超出部分。示例：
输入：
[1, 0, 2, 3, 0, 4, 5, 0]输出：
[1, 0, 0, 2, 3, 0, 0, 4]2. 算法思路
核心思想：使用双指针技术，分为两个阶段：
模拟阶段：计算复制
0后的数组长度，确定有效范围。填充阶段：从后向前填充数组，复制
0并移动元素。具体步骤：
模拟阶段：
使用
cur指针遍历数组，dest指针记录复制0后的位置。如果当前元素
arr[cur]是0，则dest增加 2（因为需要复制一个0）。如果当前元素
arr[cur]不是0，则dest增加 1。当
dest达到或超过数组长度n-1时，停止模拟。边界处理：
如果
dest恰好等于n，说明最后一个元素需要被丢弃（因为复制0会导致数组越界）。将数组最后一个元素设置为
0，并调整cur和dest指针。填充阶段：
从后向前遍历数组，根据
cur指针的值填充dest指针的位置。如果
arr[cur]是0，则复制两个0。如果
arr[cur]不是0，则直接复制该值。3. 代码逐行解析
class Solution { public:void duplicateZeros(vector<int>& arr) {int cur = 0, dest = -1, n = arr.size(); // 初始化 cur 和 dest// 模拟阶段：计算 dest 的最终位置while (cur < n) {if (arr[cur]) dest++; // 当前元素不是 0，dest 增加 1else dest += 2; // 当前元素是 0，dest 增加 2if (dest >= n - 1) break; // 如果 dest 达到或超过数组长度，停止模拟cur++;}// 边界处理：如果 dest 超出数组长度，丢弃最后一个元素if (dest == n) {arr[n - 1] = 0; // 将最后一个元素设置为 0cur--; // 回退 cur 指针dest -= 2; // 回退 dest 指针}// 填充阶段：从后向前填充数组while (cur >= 0) {if (arr[cur]) arr[dest--] = arr[cur--]; // 当前元素不是 0，直接复制else {arr[dest--] = 0; // 当前元素是 0，复制两个 0arr[dest--] = 0;cur--;}}} };4. 示例运行
以输入
[1, 0, 2, 3, 0, 4, 5, 0]为例：
模拟阶段：
cur = 0，arr[0] = 1，dest = 0。
cur = 1，arr[1] = 0，dest = 2。
cur = 2，arr[2] = 2，dest = 3。
cur = 3，arr[3] = 3，dest = 4。
cur = 4，arr[4] = 0，dest = 6。
cur = 5，arr[5] = 4，dest = 7。
cur = 6，arr[6] = 5，dest = 8（超过数组长度，停止模拟）。边界处理：
dest = 8超出数组长度，将arr[7]设置为0，并调整cur = 5，dest = 6。填充阶段：
cur = 5，arr[5] = 4，arr[6] = 4，dest = 5。
cur = 4，arr[4] = 0，arr[5] = 0，arr[4] = 0，dest = 3。
cur = 3，arr[3] = 3，arr[3] = 3，dest = 2。
cur = 2，arr[2] = 2，arr[2] = 2，dest = 1。
cur = 1，arr[1] = 0，arr[1] = 0，arr[0] = 0，dest = -1。
cur = 0，arr[0] = 1，arr[0] = 1，dest = -2。最终结果：
[1, 0, 0, 2, 3, 0, 0, 4]。5. 时间复杂度与空间复杂度
时间复杂度：O(n)，其中
n是数组的长度。每个元素最多被遍历两次。空间复杂度：O(1)，只使用了常数级别的额外空间。
6. 总结
这段代码通过双指针技术，高效地实现了在数组中复制
0的功能。其核心思想是：
模拟阶段：计算复制
0后的数组长度，确定有效范围。填充阶段：从后向前填充数组，确保复制
0的同时不覆盖未处理的元素。这种方法避免了额外的空间开销，同时保持了较高的效率。
三、202. 快乐数 - 力扣（LeetCode）
1. 问题分析
目标：判断一个整数
n是否是快乐数。快乐数的定义：
对于一个正整数，计算其每个位置上的数字的平方和。
重复这个过程，如果最终结果为
1，则是快乐数。如果进入一个不包含
1的循环，则不是快乐数。示例：
输入：
19计算过程：
1² + 9² = 82
8² + 2² = 68
6² + 8² = 100
1² + 0² + 0² = 1
输出：
true2. 算法思路
核心思想：使用快慢指针技术检测循环。
如果
n是快乐数，最终会收敛到1。如果
n不是快乐数，会进入一个循环。具体步骤：
定义一个辅助函数
Sum，用于计算一个整数的每个位置上的数字的平方和。使用快慢指针技术：
slow指针每次计算一次平方和。
fast指针每次计算两次平方和。如果
fast和slow相遇，说明存在循环。如果相遇时的值为
1，则n是快乐数；否则，不是快乐数。3. 代码逐行解析
class Solution { public:// 辅助函数：计算一个整数的每个位置上的数字的平方和int Sum(int n) {int sum = 0;while (n) {int tmp = n % 10; // 取最后一位数字sum += tmp * tmp; // 计算平方并累加n = n / 10; // 去掉最后一位数字}return sum;}// 判断一个整数是否是快乐数bool isHappy(int n) {int slow = n; // 慢指针int fast = Sum(n); // 快指针while (fast != slow) { // 快慢指针未相遇时继续循环slow = Sum(slow); // 慢指针每次计算一次平方和fast = Sum(Sum(fast)); // 快指针每次计算两次平方和}return slow == 1; // 如果相遇时的值为 1，则是快乐数} };4. 示例运行
以输入
19为例：
初始状态：
slow = 19，fast = Sum(19) = 82。第一次循环：
slow = Sum(19) = 82。
fast = Sum(Sum(82)) = Sum(68) = 100。第二次循环：
slow = Sum(82) = 68。
fast = Sum(Sum(100)) = Sum(1) = 1。第三次循环：
slow = Sum(68) = 100。
fast = Sum(Sum(1)) = Sum(1) = 1。第四次循环：
slow = Sum(100) = 1。
fast = Sum(Sum(1)) = Sum(1) = 1。循环结束，
slow == 1，返回true。5. 时间复杂度与空间复杂度
时间复杂度：O(log n)，其中
n是输入的整数。每次计算平方和的时间复杂度为 O(log n)，快慢指针的循环次数也与n的位数相关。空间复杂度：O(1)，只使用了常数级别的额外空间。
6. 总结
这段代码通过快慢指针技术，高效地判断一个整数是否是快乐数。其核心思想是：
快慢指针检测循环：通过快慢指针的移动，判断是否存在循环。
辅助函数计算平方和：通过
Sum函数计算整数的每个位置上的数字的平方和。这种方法避免了额外的空间开销，同时保持了较高的效率。
四、11. 盛最多水的容器 - 力扣（LeetCode）
1. 问题分析
目标：在数组
height中找到两条垂直线，使得它们与 x 轴构成的容器可以容纳最多的水。容器的容量：由两条垂直线之间的距离（宽度）和较短垂直线的高度决定，即
容量 = 宽度 * 高度。示例：
输入：
height = [1, 8, 6, 2, 5, 4, 8, 3, 7]输出：
49解释：选择第 2 条线（高度为 8）和第 9 条线（高度为 7），容量为
(9-2) * min(8, 7) = 7 * 7 = 49。2. 算法思路
核心思想：使用双指针技术，从数组的两端向中间移动，逐步缩小搜索范围。
具体步骤：
初始化两个指针
left和right，分别指向数组的起始位置和末尾位置。计算当前容器的容量
v = (right - left) * min(height[left], height[right])。更新最大容量
tmp = max(tmp, v)。移动指针：
如果
height[left] < height[right]，则移动left指针（因为容器的容量受限于较短的高度，移动较短的指针可能会找到更高的垂直线）。否则，移动
right指针。重复上述步骤，直到
left和right相遇。返回最大容量
tmp。3. 代码逐行解析
class Solution { public:int maxArea(vector<int>& height) {int left = 0; // 左指针int right = height.size() - 1; // 右指针int v = 0; // 当前容器的容量int tmp = 0; // 最大容量while (left < right) { // 双指针未相遇时继续循环if (height[left] < height[right]) { // 左指针高度较小v = (right - left) * height[left]; // 计算当前容量tmp = max(tmp, v); // 更新最大容量left++; // 移动左指针} else { // 右指针高度较小或相等v = (right - left) * height[right]; // 计算当前容量tmp = max(tmp, v); // 更新最大容量right--; // 移动右指针}}return tmp; // 返回最大容量} };4. 示例运行
以输入
height = [1, 8, 6, 2, 5, 4, 8, 3, 7]为例：
初始状态：
left = 0，right = 8，tmp = 0。第一次循环：
height[left] = 1，height[right] = 7。计算容量
v = (8 - 0) * 1 = 8。更新
tmp = max(0, 8) = 8。移动
left指针，left = 1。第二次循环：
height[left] = 8，height[right] = 7。计算容量
v = (8 - 1) * 7 = 49。更新
tmp = max(8, 49) = 49。移动
right指针，right = 7。第三次循环：
height[left] = 8，height[right] = 3。计算容量
v = (7 - 1) * 3 = 18。更新
tmp = max(49, 18) = 49。移动
right指针，right = 6。第四次循环：
height[left] = 8，height[right] = 8。计算容量
v = (6 - 1) * 8 = 40。更新
tmp = max(49, 40) = 49。移动
left指针，left = 2。循环结束，返回
tmp = 49。5. 时间复杂度与空间复杂度
时间复杂度：O(n)，其中
n是数组的长度。双指针最多遍历数组一次。空间复杂度：O(1)，只使用了常数级别的额外空间。
6. 总结
这段代码通过双指针技术，高效地解决了盛最多水的容器问题。其核心思想是：
双指针缩小搜索范围：通过移动较短的指针，逐步缩小搜索范围，确保不漏掉可能的更大容量。
容量计算：根据两条垂直线之间的距离和较短的高度计算容量。
这种方法避免了暴力搜索的高时间复杂度（O(n^2)），将问题优化为线性时间复杂度。
五、611. 有效三角形的个数 - 力扣（LeetCode）
1. 问题分析
目标：在数组
nums中找到所有满足三角形条件的三元组(nums[i], nums[j], nums[k])，即nums[i] + nums[j] > nums[k]、nums[i] + nums[k] > nums[j]和nums[j] + nums[k] > nums[i]。三角形条件：对于任意三条边，较短的两条边之和必须大于第三条边。
示例：
输入：
nums = [2, 2, 3, 4]输出：
3解释：有效的三元组为
(2, 3, 4)、(2, 3, 4)和(2, 2, 3)。2. 算法思路
核心思想：利用排序和双指针技术，将问题转化为固定最长边，然后在剩余部分中寻找满足条件的两条较短边。
具体步骤：
排序：将数组
nums排序，方便后续操作。固定最长边：从数组的末尾开始，依次固定最长边
nums[i]。双指针查找：
使用双指针
left和right，分别指向数组的起始位置和最长边的左侧位置。如果
nums[left] + nums[right] > nums[i]，则说明从left到right-1的所有元素都可以与nums[right]和nums[i]组成有效三角形，因此累加right - left到结果中，并移动right指针。否则，移动
left指针，尝试找到更大的较短边。重复上述步骤，直到所有最长边都被处理完毕。
3. 代码逐行解析
class Solution { public:int triangleNumber(vector<int>& nums) {sort(nums.begin(), nums.end()); // 对数组进行排序int sum = 0; // 统计有效三角形的个数int n = nums.size(); // 数组的长度for (int i = n - 1; i >= 2; i--) { // 固定最长边 nums[i]int left = 0; // 左指针int right = i - 1; // 右指针while (left < right) { // 双指针未相遇时继续循环if (nums[left] + nums[right] > nums[i]) { // 满足三角形条件sum += (right - left); // 累加有效三角形的个数right--; // 移动右指针} else { // 不满足三角形条件left++; // 移动左指针}}}return sum; // 返回有效三角形的个数} };4. 示例运行
以输入
nums = [2, 2, 3, 4]为例：
排序后数组：
[2, 2, 3, 4]。固定最长边
nums[3] = 4：
left = 0，right = 2。
nums[left] + nums[right] = 2 + 3 = 5 > 4，满足条件，累加right - left = 2到sum，sum = 2。移动
right指针，right = 1。
nums[left] + nums[right] = 2 + 2 = 4 <= 4，不满足条件，移动left指针，left = 1。循环结束。
固定最长边
nums[2] = 3：
left = 0，right = 1。
nums[left] + nums[right] = 2 + 2 = 4 > 3，满足条件，累加right - left = 1到sum，sum = 3。移动
right指针，right = 0。循环结束。
返回结果：
sum = 3。5. 时间复杂度与空间复杂度
时间复杂度：O(n^2)，其中
n是数组的长度。排序的时间复杂度为 O(n log n)，双指针的循环时间复杂度为 O(n^2)。空间复杂度：O(1)，只使用了常数级别的额外空间。
6. 总结
这段代码通过排序和双指针技术，高效地解决了有效三角形的个数问题。其核心思想是：
排序：将数组排序，方便固定最长边。
双指针查找：固定最长边后，使用双指针在剩余部分中寻找满足条件的两条较短边。
这种方法避免了暴力搜索的高时间复杂度（O(n^3)），将问题优化为 O(n^2) 的时间复杂度。
六、 LCR 179. 查找总价格为目标值的两个商品 - 力扣（LeetCode）
1. 问题分析
目标：在有序数组
price中找到两个数，使它们的和等于target。输入：
price：一个升序排列的整数数组。
target：目标值。输出：返回两个数的值，如果不存在这样的两个数，则返回
{-1, -1}。示例：
输入：
price = [2, 7, 11, 15]，target = 9输出：
[2, 7]2. 算法思路
核心思想：利用数组的有序性，使用双指针技术从数组的两端向中间移动，逐步缩小搜索范围。
具体步骤：
初始化两个指针
left和right，分别指向数组的起始位置和末尾位置。计算当前两个指针指向的数的和
sum = price[left] + price[right]。比较
sum与target：
如果
sum > target，说明当前和过大，需要减小和，因此将right指针左移。如果
sum < target，说明当前和过小，需要增大和，因此将left指针右移。如果
sum == target，说明找到了满足条件的两个数，直接返回它们的值。重复上述步骤，直到
left和right指针相遇。如果未找到满足条件的两个数，返回
{-1, -1}。3. 代码逐行解析
class Solution { public:vector<int> twoSum(vector<int>& price, int target) {int left = 0; // 左指针，指向数组的起始位置int right = price.size() - 1; // 右指针，指向数组的末尾位置while (left < right) { // 双指针未相遇时继续循环int sum = price[left] + price[right]; // 计算当前两个数的和if (sum > target) { // 如果和大于目标值right--; // 右指针左移，减小和} else if (sum < target) { // 如果和小于目标值left++; // 左指针右移，增大和} else { // 如果和等于目标值return {price[left], price[right]}; // 返回满足条件的两个数}}return {-1, -1}; // 如果未找到，返回 {-1, -1}} };4. 示例运行
以输入
price = [2, 7, 11, 15]，target = 9为例：
初始状态：
left = 0，right = 3。
price[left] = 2，price[right] = 15。第一次循环：
sum = 2 + 15 = 17。
sum > target，右指针左移，right = 2。第二次循环：
sum = 2 + 11 = 13。
sum > target，右指针左移，right = 1。第三次循环：
sum = 2 + 7 = 9。
sum == target，返回[2, 7]。5. 时间复杂度与空间复杂度
时间复杂度：O(n)，其中
n是数组的长度。双指针最多遍历数组一次。空间复杂度：O(1)，只使用了常数级别的额外空间。
6. 总结
这段代码通过双指针技术，高效地解决了有序数组中的两数之和问题。其核心思想是：
利用有序性：通过数组的有序性，快速缩小搜索范围。
双指针移动：根据当前和与目标值的大小关系，决定移动哪个指针。
这种方法避免了暴力搜索的高时间复杂度（O(n^2)），将问题优化为线性时间复杂度。
七、15. 三数之和 - 力扣（LeetCode）
1. 问题分析
目标：在数组
nums中找到所有满足nums[i] + nums[j] + nums[k] = 0的三元组，且三元组不重复。输入：一个整数数组
nums。输出：所有满足条件的三元组，存储在
vector<vector<int>>中。示例：
输入：
nums = [-1, 0, 1, 2, -1, -4]输出：
[[-1, -1, 2], [-1, 0, 1]]2. 算法思路
核心思想：利用排序和双指针技术，将三数之和问题转化为两数之和问题。
具体步骤：
排序：将数组
nums排序，方便后续操作。固定第一个数：遍历数组，固定第一个数
nums[i]。
如果
nums[i] > 0，则直接退出循环（因为数组已排序，后面的数都大于 0，无法满足三数之和为 0）。双指针查找：
使用双指针
left和right，分别指向i+1和n-1。计算目标值
target = -nums[i]，即nums[left] + nums[right] = target。如果
nums[left] + nums[right] == target，则找到一个满足条件的三元组，将其加入结果集，并移动left和right指针。如果
nums[left] + nums[right] > target，则移动right指针。如果
nums[left] + nums[right] < target，则移动left指针。去重操作：
在固定第一个数
nums[i]时，跳过重复的值。在找到满足条件的三元组后，跳过
left和right指针指向的重复值。返回结果：最终返回所有满足条件的三元组。
3. 代码逐行解析
class Solution { public:vector<vector<int>> threeSum(vector<int>& nums) {sort(nums.begin(), nums.end()); // 对数组进行排序int n = nums.size(); // 数组的长度vector<vector<int>> ret; // 存储结果的三元组for (int i = 0; i < n;) { // 固定第一个数 nums[i]if (nums[i] > 0) break; // 如果 nums[i] > 0，直接退出循环int left = i + 1; // 左指针int right = n - 1; // 右指针int target = -nums[i]; // 目标值while (left < right) { // 双指针未相遇时继续循环if (nums[left] + nums[right] == target) { // 找到满足条件的三元组ret.push_back({nums[i], nums[left], nums[right]}); // 加入结果集left++, 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) { // 和大于目标值right--; // 移动右指针// 去重操作：跳过 right 指向的重复值if ((left < right) && (nums[right] == nums[right + 1])) right--;} else { // 和小于目标值left++; // 移动左指针// 去重操作：跳过 left 指向的重复值if ((left < right) && (nums[left] == nums[left - 1])) left++;}}i++; // 移动固定数的指针// 去重操作：跳过 i 指向的重复值while ((i < n) && (nums[i] == nums[i - 1])) i++;}return ret; // 返回结果} };4. 示例运行
以输入
nums = [-1, 0, 1, 2, -1, -4]为例：
排序后数组：
[-4, -1, -1, 0, 1, 2]。固定第一个数
nums[0] = -4：
left = 1，right = 5。
target = 4。
nums[left] + nums[right] = -1 + 2 = 1 < 4，移动left指针。
left = 2，nums[left] + nums[right] = -1 + 2 = 1 < 4，移动left指针。
left = 3，nums[left] + nums[right] = 0 + 2 = 2 < 4，移动left指针。
left = 4，nums[left] + nums[right] = 1 + 2 = 3 < 4，移动left指针。循环结束。
固定第一个数
nums[1] = -1：
left = 2，right = 5。
target = 1。
nums[left] + nums[right] = -1 + 2 = 1 == target，找到三元组[-1, -1, 2]，加入结果集。移动
left和right指针，left = 3，right = 4。
nums[left] + nums[right] = 0 + 1 = 1 == target，找到三元组[-1, 0, 1]，加入结果集。移动
left和right指针，left = 4，right = 3，循环结束。固定第一个数
nums[2] = -1：
跳过重复值。
固定第一个数
nums[3] = 0：
left = 4，right = 5。
target = 0。
nums[left] + nums[right] = 1 + 2 = 3 > 0，移动right指针。循环结束。
返回结果：
[[-1, -1, 2], [-1, 0, 1]]。5. 时间复杂度与空间复杂度
时间复杂度：O(n^2)，其中
n是数组的长度。排序的时间复杂度为 O(n log n)，双指针的循环时间复杂度为 O(n^2)。空间复杂度：O(1)，忽略结果集的空间，只使用了常数级别的额外空间。
6. 总结
这段代码通过排序和双指针技术，高效地解决了三数之和问题。其核心思想是：
排序：将数组排序，方便固定第一个数。
双指针查找：固定第一个数后，使用双指针在剩余部分中寻找满足条件的两数。
去重操作：通过跳过重复值，确保结果集中不包含重复的三元组。
这种方法避免了暴力搜索的高时间复杂度（O(n^3)），将问题优化为 O(n^2) 的时间复杂度。
八、18. 四数之和 - 力扣（LeetCode）
1. 问题分析
目标：在数组
nums中找到所有满足nums[i] + nums[j] + nums[k] + nums[l] = target的四元组，且四元组不重复。输入：
nums：一个整数数组。
target：目标值。输出：所有满足条件的四元组，存储在
vector<vector<int>>中。示例：
输入：
nums = [1, 0, -1, 0, -2, 2]，target = 0输出：
[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]2. 算法思路
核心思想：利用排序和双指针技术，将四数之和问题转化为三数之和问题，再进一步转化为两数之和问题。
具体步骤：
排序：将数组
nums排序，方便后续操作。固定前两个数：
使用两层循环，分别固定前两个数
nums[i]和nums[j]。在固定
nums[i]和nums[j]后，问题转化为在剩余部分中找到两个数nums[left]和nums[right]，使得nums[left] + nums[right] = target - nums[i] - nums[j]。双指针查找：
使用双指针
left和right，分别指向j+1和n-1。计算目标值
sum = target - nums[i] - nums[j]。如果
nums[left] + nums[right] == sum，则找到一个满足条件的四元组，将其加入结果集，并移动left和right指针。如果
nums[left] + nums[right] < sum，则移动left指针。如果
nums[left] + nums[right] > sum，则移动right指针。去重操作：
在固定
nums[i]和nums[j]时，跳过重复的值。在找到满足条件的四元组后，跳过
left和right指针指向的重复值。返回结果：最终返回所有满足条件的四元组。
3. 代码逐行解析
class Solution { public:vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> ret; // 存储结果的四元组sort(nums.begin(), nums.end()); // 对数组进行排序int n = nums.size(); // 数组的长度for (int i = 0; i < n;) { // 固定第一个数 nums[i]for (int j = i + 1; j < n;) { // 固定第二个数 nums[j]int left = j + 1; // 左指针int right = n - 1; // 右指针long long sum = (long long)target - nums[i] - nums[j]; // 目标值while (left < right) { // 双指针未相遇时继续循环int tmp = nums[left] + nums[right]; // 当前两个数的和if (tmp < sum) { // 和小于目标值left++; // 移动左指针} else if (tmp > sum) { // 和大于目标值right--; // 移动右指针} else { // 和等于目标值ret.push_back({nums[i], nums[j], nums[left], nums[right]}); // 加入结果集left++, right--; // 移动指针// 去重操作：跳过 left 和 right 指向的重复值while (left < right && nums[left] == nums[left - 1]) left++;while (left < right && nums[right] == nums[right + 1]) right--;}}j++; // 移动第二个数的指针// 去重操作：跳过 j 指向的重复值while (j < n && nums[j] == nums[j - 1]) j++;}i++; // 移动第一个数的指针// 去重操作：跳过 i 指向的重复值while (i < n && nums[i] == nums[i - 1]) i++;}return ret; // 返回结果} };4. 示例运行
以输入
nums = [1, 0, -1, 0, -2, 2]，target = 0为例：
排序后数组：
[-2, -1, 0, 0, 1, 2]。固定第一个数
nums[0] = -2：
固定第二个数
nums[1] = -1：
left = 2，right = 5。
sum = 0 - (-2) - (-1) = 3。
nums[left] + nums[right] = 0 + 2 = 2 < 3，移动left指针。
left = 3，nums[left] + nums[right] = 0 + 2 = 2 < 3，移动left指针。
left = 4，nums[left] + nums[right] = 1 + 2 = 3 == sum，找到四元组[-2, -1, 1, 2]，加入结果集。移动
left和right指针，left = 5，right = 4，循环结束。固定第二个数
nums[2] = 0：
left = 3，right = 5。
sum = 0 - (-2) - 0 = 2。
nums[left] + nums[right] = 0 + 2 = 2 == sum，找到四元组[-2, 0, 0, 2]，加入结果集。移动
left和right指针，left = 4，right = 4，循环结束。固定第一个数
nums[1] = -1：
固定第二个数
nums[2] = 0：
left = 3，right = 5。
sum = 0 - (-1) - 0 = 1。
nums[left] + nums[right] = 0 + 2 = 2 > 1，移动right指针。
right = 4，nums[left] + nums[right] = 0 + 1 = 1 == sum，找到四元组[-1, 0, 0, 1]，加入结果集。移动
left和right指针，left = 4，right = 3，循环结束。返回结果：
[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]。5. 时间复杂度与空间复杂度
时间复杂度：O(n^3)，其中
n是数组的长度。排序的时间复杂度为 O(n log n)，双指针的循环时间复杂度为 O(n^3)。空间复杂度：O(1)，忽略结果集的空间，只使用了常数级别的额外空间。
6. 总结
这段代码通过排序和双指针技术，高效地解决了四数之和问题。其核心思想是：
排序：将数组排序，方便固定前两个数。
双指针查找：固定前两个数后，使用双指针在剩余部分中寻找满足条件的两数。
去重操作：通过跳过重复值，确保结果集中不包含重复的四元组。
这种方法避免了暴力搜索的高时间复杂度（O(n^4)），将问题优化为 O(n^3) 的时间复杂度。
相关文章：
双指针（典型算法思想）——OJ例题算法解析思路
目录 一、283. 移动零 - 力扣（LeetCode） 1. 问题分析 2. 算法思路 3. 代码逐行解析 4. 示例运行 5. 时间复杂度与空间复杂度 6. 总结 二、1089. 复写零 - 力扣（LeetCode） 1. 问题分析 2. 算法思路 3. 代码逐行解析 4. …...
大数据Hadoop入门1
目录 相关资料 第一部分 1.课程内容大纲和学习目标 2.数据分析和企业数据分析方向 3.数据分析基本流程步骤 4.大数据时代 5.分布式和集群 6.Linux操作系统概述 7.VMware虚拟机概念与安装 8.centos操作系统的虚拟机导入 9.VMware虚拟机常规使用、快照 第二部分 1.课…...
Ubuntu-手动安装 SBT
文章目录 前言Ubuntu-手动安装 SBT1. SBT是什么?1.1. SBT 的特点1.2. SBT 的基本功能1.3. SBT 的常用命令 2. 安装2.1. 下载2.2. 解压 sbt 二进制包2.3. 确认 sbt 可执行文件的位置2.4. 设置执行权限2.5. 创建符号链接2.6. 更新 PATH 环境变量2.7. 验证 sbt 安装 前言 如果您觉…...
人工智能：农业领域的变革力量
在当今科技飞速发展的时代，人工智能正以前所未有的态势渗透进各个领域，农业也不例外。想象一下，未来的农田里，农民不再是弯腰劳作的形象，而是坐在高科技的“智能农场”里，悠闲地喝着咖啡，指挥着…...
Qt——界面优化
一.QSS 1.背景 在网页前端开发领域中， CSS 是⼀个至关重要的部分。 描述了⼀个网页的 "样式"。 从而起到对网页美化的作用。 所谓样式，包括不限于大小，位置，颜色，背景，间距，字体等等…...
Qt Designer and Python: Build Your GUI
1.install pyside6 2.pyside6-designer.exe 发送到桌面快捷方式 在Python安装的所在 Scripts 文件夹下找到此文件。如C:\Program Files\Python312\Scripts 3. 打开pyside6-designer 设计UI 4.保存为simple.ui 文件，再转成py文件 用代码执行 pyside6-uic.exe simpl…...
HarmonyOS DevEco Studio模拟器点击运行没有反应的解决方法
HarmonyOS DevEco Studio模拟器点击运行没有反应的解决方法 翻遍了CSDN，试了所有办法都没办法，最后偶然间竟然解决了 解决方法其实很简单：本地模拟器下载路径下面不能有中文。。。。。 切换正确路径以后，成功运行，哦…...
java中的算数运算符
1.java中的加法是“”。 简单数字的相加对于byte.short.char.int类型数字相加时进行整形提升至int,对于数据类型大于int的long.float.double数据类型有参与计算时，需要进行整形提升至最高的数据类型。 有字符串类型的相加，将数字视为字符串进行字符串的…...
【数据结构】二叉树
二叉树 1. 树型结构（了解）1.1 概念1.2 概念（重要）1.3 树的表示形式（了解）1.4 树的应用 2. 二叉树（重点）2.1 概念2.2 两种特殊的二叉树2.3 二叉树的性质2.4 二叉树的存储2.5 二叉树的…...
websocket实现
由于安卓资源管理器展示的路径不尽相同,各种软件保存文件的位置也不一定一样.对于普通用户上传文件时,查找文件可能是一个麻烦的事情.后来想到了一个办法,使用pc端进行辅助上传. 文章目录 实现思路1.0 实现定义web与客户端通信数据类型和数据格式web端websocket实现web端对客户…...
AI软件外包需要注意什么 外包开发AI软件的关键因素是什么 如何选择AI外包开发语言
1. 定义目标与需求 首先，要明确你希望AI智能体做什么。是自动化任务、数据分析、自然语言处理，还是其他功能？明确目标可以帮助你选择合适的技术和方法。 2. 选择开发平台与工具 开发AI智能体的软件时，你需要选择适合的编程语言、…...
电梯系统的UML文档12
5.2.1 DoorControl 的状态图 图 19: DoorControl 的状态图 5.2.2 DriveControl 的状态图 图 20: DriveControl 的状态图 5.2.3 LanternControl 的状态图 图 21: LanternControl 的状态图 5.2.4 HallButtonControl 的状态图 图 22: HallButtonControl 的状态图 5.2.5 CarB…...
【华为路由的arp配置】
华为路由的arp配置 ARP：IP地址与MAC地址的映射。 R1: g0/0/0:10.1.1.254/24 g0/0/1:10.1.2.254/24 PC1: 10.1.1.1/16 PC2: 10.1.1.2/16 PC3: 10.1.2.3/16 动态ARP 查看PC1的arp表，可以看到，列表为空。 查看R1的arp表 在PC3上ping命令测…...
Web 代理、爬行器和爬虫
目录 Web 在线网页代理服务器的使用方法Web 在线网页代理服务器使用流程详解注意事项 Web 请求和响应中的代理方式Web 开发中的请求方法借助代理进行文件下载的示例 Web 服务器请求代理方式代理、网关和隧道的概念参考文献说明 爬虫的工作原理及案例网络爬虫概述爬虫工作原理 W…...
node 爬虫开发内存处理 zp_stoken 作为案例分析
声明: 本文章中所有内容仅供学习交流使用，不用于其他任何目的，抓包内容、敏感网址、数据接口等均已做脱敏处理，严禁用于商业用途和非法用途，否则由此产生的一切后果均与作者无关！ 前言 主要说3种我们补环境过后如果用…...
【Samba】Ubuntu20.04 Windows 共享文件夹
【Samba】Ubuntu20.04 Windows 共享文件夹 前言整体思路检查 Ubuntu 端 和 Windows 网络通信是否正常创建共享文件夹安装并配置 Samba 服务器安装 Samba 服务器创建 Samba 用户编辑 Samba 配置文件重启 Samba 服务器 在 Windows 端 访问 Ubuntu 的共享文件夹 前言 本文基于 Ub…...
windows下本地部署安装hadoop+scala+spark-【不需要虚拟机】
注意版本依赖【本实验版本如下】 Hadoop 3.1.1 spark 2.3.2 scala 2.11 1.依赖环境 1.1 java 安装java并配置环境变量【如果未安装搜索其他教程】 环境验证如下： C:\Users\wangning>java -version java version "1.8.0_261" Java(TM) SE Runti…...
GitHub 仓库的 Archived 功能详解：中英双语
GitHub 仓库的 Archived 功能详解 一、什么是 GitHub 仓库的 “Archived” 功能？ 在 GitHub 上，“Archived” 是一个专门用于标记仓库状态的功能。当仓库被归档后，它变为只读模式，所有的功能如提交代码、创建 issue 和 pull req…...
银行卡三要素验证接口：方便快捷地实现银行卡核验功能
银行卡三要素验证API：防止欺诈交易的有力武器 随着互联网的发展，电子支付方式也越来越普及。在支付过程中，银行卡是最常用的支付工具之一。然而，在一些支付场景中，需要对用户的银行卡信息进行验证，以确保支…...
Banana JS，一个严格子集 JavaScript 的解释器
项目地址：https://github.com/shajunxing/banana-js 特色 我的目标是剔除我在实践中总结的JavaScript语言的没用的和模棱两可的部分，只保留我喜欢和需要的，创建一个最小的语法解释器。只支持 JSON 兼容的数据类型和函数，函数是第…...
引领未来科技潮流：Web3 前沿发展趋势
随着技术不断发展，我们正站在一个全新的互联网时代的门槛上，Web3的出现正在重新定义互联网的构架和运作方式。Web3，作为互联网的下一代发展趋势，其核心思想是去中心化、开放与用户主权。与现有的Web2.0相比，Web3更加注…...
OpenCV：在图像中添加高斯噪声、胡椒噪声
目录 在图像中添加高斯噪声 高斯噪声的特性 添加高斯噪声的实现 给图像添加胡椒噪声 实现胡椒噪声的步骤 相关阅读 OpenCV：图像处理中的低通滤波-CSDN博客 OpenCV：高通滤波之索贝尔、沙尔和拉普拉斯-CSDN博客 OpenCV：图像滤波、卷积与…...
 20中安装Nvidia驱动)
在深度Linux (Deepin) 20中安装Nvidia驱动
文章创作不易，麻烦大家点赞关注收藏一键三连。 在Deepin上面跑Tensorflow, pytorch等人工智能框架不是一件容易的事情。特别是如果你要使用GPU，就得有nvidia的驱动。默认情况下Deepin系统自带的是nouveau开源驱动。这是没办法用tensorflow的。下面内容是…...
PC端实现PDF预览（支持后端返回文件流 || 返回文件URL）
一、使用插件 插件名称：vue-office/pdf 版本：2.0.2 安装插件：npm i vue-office/pdf^2.0.2 1、“vue-office/pdf”: “^2.0.2”, 2、 npm i vue-office/pdf^2.0.2 二、代码实现 // 引入组件 （在需要使用的页面中直接引入&#x…...
【ESP32】ESP-IDF开发 | WiFi开发 | UDP用户数据报协议 + UDP客户端和服务器例程
1. 简介 UDP协议（User Datagram Protocol），全称用户数据报协议，它是一种面向非连接的协议，面向非连接指的是在正式通信前不必与对方先建立连接， 不管对方状态就直接发送。至于对方是否可以接收到这些数据内…...
OpenAI的真正对手？DeepSeek-R1如何用强化学习重构LLM能力边界——DeepSeek-R1论文精读
2025年1月20日，DeepSeek-R1 发布，并同步开源模型权重。截至目前，DeepSeek 发布的 iOS 应用甚至超越了 ChatGPT 的官方应用，直接登顶 AppStore。 DeepSeek-R1 一经发布，各种资讯已经铺天盖地，那就让我们一起…...
es数据同步
Logstash 是 Elastic 技术栈中的一个技术，它是一个数据采集引擎，可以从数据库采集数据到 ES 中。可以通过设置 自增 ID 主键 或 更新时间 来控制数据的自动同步： 自增 ID 主键：Logstatsh 会有定时任务，如果发现有主键…...
【JavaScript笔记】01- 原型及原型链（面试高频内容）
前言 JavaScript作为前端入门三件套之一，也是前端求职的必会知识，重要性不言而喻。 这个系列分享个人学习JavaScript的记录，和大家一起学习讨论。 下面介绍关于原型&原型链的相关重要知识点。 1、构造函数创建对象 function Student(…...
【Python】第五弹---深入理解函数：从基础到进阶的全面解析
✨个人主页： 熬夜学编程的小林 💗系列专栏： 【C语言详解】 【数据结构详解】【C详解】【Linux系统编程】【MySQL】【Python】 目录 1、函数 1.1、函数是什么 1.2、语法格式 1.3、函数参数 1.4、函数返回值 1.5、变量作用域 1.6、函数…...
动态规划DP 数字三角形模型（模型分析+例题分析+C++代码实现）（数字三角形、摘花生、最低通行费用、方格取数、传纸条）
总体概览 数字三角形 原题链接 AcWing 898.数字三角形 题目描述 给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路…...
2025 最新flutter面试总结
目录 1.Dart是值传递还是引用传递？ 2.Flutter 是单引擎还是双引擎 3. StatelessWidget 和 StatefulWidget 在 Flutter 中有什么区别？ 4.简述Dart语音特性 5. Navigator 是什么？在 Flutter 中 Routes 是什么？ 6、Dart 是不是…...
Java后端之AOP
AOP：面向切面编程，本质是面向特定方法编程 引入依赖： <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-aop</artifactId></dependency>示例：记录…...
JS中对数组的操作哪些会改变原数组哪些不会？今天你一定要记下！
JavaScript 数组方法：变更原数组与不变更原数组的区别 在 JavaScript 中，数组是非常常见且重要的数据结构。作为开发者，我们常常需要使用数组方法来处理数组数据。但是，数组的不同方法会以不同的方式影响原数组，它们可…...
ubuntu x64下交叉编译ffmpeg到目标架构为aarch架构的系统
参考链接 https://blog.csdn.net/qq_46396470/article/details/137794498...
Java进阶（二）：Java设计模式
目录 设计模式 一.建模语言 二.类之间的关系 1.依赖关系 2.关联关系 3.聚合关系 4.组合关系 5.继承关系 6.实现关系 三.面向对象设计原则 单一职责原则 开闭原则 里氏替换原则 依赖倒置 接口隔离原则 迪米特原则 组合/聚合(关联关系)复用原则 四.23种设计模式…...
函数实现多图像叠加)
python学opencv|读取图像（四十二）使用cv2.add()函数实现多图像叠加
【1】引言 前序学习过程中，掌握了灰度图像和彩色图像的掩模操作： python学opencv|读取图像（九）用numpy创建黑白相间灰度图_numpy生成全黑图片-CSDN博客 python学opencv|读取图像（四十）掩模：三…...
DIY QMK量子键盘
最近放假了，趁这个空余在做一个分支项目，一款机械键盘，量子键盘取自固件名称QMK（Quantum Mechanical Keyboard）。 键盘作为计算机或其他电子设备的重要输入设备之一，通过将按键的物理动作转换为数字信号&am…...
【公式】卢布贬值风险：义乌到俄罗斯贸易的汇率陷阱
卢布贬值风险：义乌到俄罗斯贸易的汇率陷阱 具体实例与推演 假设一位中国义乌的商人，计划出口一批价值100万人民币的商品到俄罗斯。最初的汇率是1人民币兑换100卢布。 初始状态： 商品价值：100万人民币初始汇率：1人民币…...
1月27（信息差）
🌍喜大普奔，适用于 VS Code 的 GitHub Copilot 全新免费版本正式推出，GitHub 全球开发者突破1.5亿 🎄Kimi深夜炸场：满血版多模态o1级推理模型！OpenAI外全球首次！Jim Fan：同天两款国…...
Linux常见问题解决方法--1
常见安全工具、设备 工具 端口及漏洞扫描：Namp、Masscan 抓包：Wireshark，Burpsuite、Fiddler、HttpCanary Web自动化安全扫描：Nessus、Awvs、Appscan、Xray 信息收集：Oneforall、hole 漏洞利用：MSF、…...
Python 数据清洗与处理常用方法全解析
在数据处理与分析过程中，缺失值、重复值、异常值等问题是常见的挑战。本文总结了多种数据清洗与处理方法：缺失值处理包括删除缺失值、固定值填充、前后向填充以及删除缺失率高的列；重复值处理通过删除或标记重复项解决数据冗余问题࿱…...
《企业应用架构模式》笔记
领域逻辑 表模块和数据集一起工作-> 先查询出一个记录集，再根据数据集生成一个（如合同）对象，然后调用合同对象的方法。 这看起来很想service查询出一个对象，但调用的是对象的方法，这看起来像是充血模型…...
顶刊JFR｜ROLO-SLAM：首个针对不平坦路面的车载Lidar SLAM系统
摘要 基于激光雷达（LiDAR）的同步定位与地图构建（SLAM）被认为是在恶劣环境中提供定位指导的一种有效方法。然而，现成的基于激光雷达的SLAM方法在经过不平坦地形时，尤其是在垂直方向相关的部分，会…...
第05章 09 使用Lookup绘制地形数据高程着色图
在VTK（Visualization Toolkit）中，可以使用颜色查找表（Lookup Table，简称LUT）来根据高程数据对地形进行着色。以下是一个示例代码，展示了如何使用VTK和C来读取地形数据，并使用颜色查找…...
)
【深度学习入门_机器学习理论】K近邻法(KNN)
本部分主要为机器学习理论入门_K近邻法(KNN)，书籍参考 “ 统计学习方法（第二版）”。 学习目标： 了解k近邻算法的基本概念、原理、应用；熟悉k近邻算法重要影响要素；熟悉kd树原理与优化应用。 开始本算法之…...
基于Django的Boss直聘IT岗位可视化分析系统的设计与实现
【Django】基于Django的Boss直聘IT岗位可视化分析系统的设计与实现（完整系统源码开发笔记详细部署教程）✅ 目录 一、项目简介二、项目界面展示三、项目视频展示 一、项目简介 该系统采用Python作为主要开发语言，利用Django这一高效、安全的W…...
编程语言中的常见Bug及解决方案
在编程过程中，不同语言有其独特的特性和挑战，这也导致了各种常见Bug的出现。本文将总结几种主流编程语言中的常见Bug，包括JavaScript、Python、C/C、Java和Go，并提供相应的解决方案和案例。 一、JavaScript中小数相加精度不准确的…...
DeepSeek API 的获取与对话示例
代码文件下载：Code 在线链接：Kaggle | Colab 文章目录 注册并获取API环境依赖设置 API单轮对话多轮对话流式输出更换模型 注册并获取API 访问 https://platform.deepseek.com/sign_in 进行注册并登录： 新用户注册后将赠送 10 块钱余额&#…...
数据库SQLite和SCADA DIAView应用教程
课程简介 此系列课程大纲主要包含七个课时。主要使用到的开发工具有：SQLite studio 和 SCADA DIAView。详细的可成内容大概如下： 1、SQLite 可视化管理工具SQLite Studio ：打开数据库和查询数据；查看视频 2、创建6个变量&#x…...
Elasticsearch+kibana安装(简单易上手）
下载ES( Download Elasticsearch | Elastic ) 将ES安装包解压缩 解压后目录如下: 修改ES服务端口（可以不修改） 启动ES 记住这些内容 验证ES是否启动成功 下载kibana( Download Kibana Free | Get Started Now | Elastic ) 解压后的kibana目…...