企业官网建设流程全解析

建设外贸公司网站,泰安焦点网络,足球比赛直播网,网推怎么做问题描述三数之和#xff08;3Sum#xff09;是一个经典的算法问题#xff1a;给定一个包含 n 个整数的数组 nums#xff0c;判断 nums 中是否存在三个元素 a, b, c#xff0c;使得 a b c 0#xff1f;找出所有满足条件且不重复的三元组。解决方案思路1. 核心思路这个…问题描述三数之和3Sum是一个经典的算法问题给定一个包含 n 个整数的数组 nums判断 nums 中是否存在三个元素 a, b, c使得 a b c 0找出所有满足条件且不重复的三元组。解决方案思路1. 核心思路这个问题最直接的暴力解法需要 O(n³) 的时间复杂度显然是不可取的。本文介绍的解决方案采用了以下优化策略排序首先将数组排序这样可以将时间复杂度降低到 O(n²)固定一个数遍历数组每次固定一个数 nums[i]双指针查找使用左右指针在固定数右侧的区间内查找另外两个数2. 算法步骤cppvectorvectorint threeSum(vectorint nums) { vectorvectorint res; sort(nums.begin(), nums.end()); // 1. 排序 int n nums.size(); for (int i 0; i n; i) { // 2. 提前终止如果当前数大于0三数之和不可能为0 if (nums[i] 0) break; // 3. 去重跳过重复的固定数 if (i 0 nums[i] nums[i-1]) continue; // 4. 双指针查找 int left i 1; int right n - 1; while (left right) { int sum nums[i] nums[left] nums[right]; if (sum 0) { // 找到有效三元组 res.push_back({nums[i], nums[left], nums[right]}); // 去重跳过左右指针的重复值 while (left right nums[left] nums[left1]) left; while (left right nums[right] nums[right-1]) right--; // 移动指针继续寻找 left; right--; } else if (sum 0) { left; // 和太小左指针右移 } else { right--; // 和太大右指针左移 } } } return res; }关键点解析1. 排序的重要性排序是此算法的基础它带来了三个好处可以使用双指针技巧将查找两个数的时间复杂度从 O(n²) 降为 O(n)便于去重操作可以提前终止搜索当固定数大于0时2. 去重处理去重是解决三数之和问题的关键代码中实现了两种去重固定数的去重cppif (i 0 nums[i] nums[i-1]) continue;跳过相同的固定数避免重复的三元组。左右指针的去重cppwhile (left right nums[left] nums[left1]) left; while (left right nums[right] nums[right-1]) right--;在找到有效三元组后跳过左右指针指向的重复值。3. 双指针的移动逻辑当三数之和等于0时记录结果并同时移动左右指针当三数之和小于0时说明需要更大的数左指针右移当三数之和大于0时说明需要更小的数右指针左移复杂度分析时间复杂度排序O(n log n)外层循环O(n)内层双指针循环O(n)总体O(n²)空间复杂度除了输出结果外只使用了常量级额外空间O(1)如果考虑存储结果的空间O(k)其中 k 是结果数量示例演示以数组[-1, 0, 1, 2, -1, -4]为例排序后[-4, -1, -1, 0, 1, 2]固定 -4在 [-1, -1, 0, 1, 2] 中查找两数之和为4 → 无解固定第二个 -1跳过第一个 -1 的重复在 [-1, 0, 1, 2] 中查找两数之和为1找到 [-1, 0, 1] 和 [-1, -1, 2]边界情况考虑数组长度小于3直接返回空结果所有数都为正或都为负不可能有三数之和为0大量重复元素去重逻辑确保结果不重复溢出问题虽然题目未明确但实际应用中需要考虑整数溢出扩展与变种最接近的三数之和找到和与目标最接近的三个数四数之和类似的思路可以扩展到四数之和问题三数之和为任意目标值将0改为任意目标值总结三数之和问题展示了如何通过排序和双指针技巧将 O(n³) 的暴力解法优化到 O(n²)。这个解决方案的关键在于排序预处理固定一个数转化为两数之和问题双指针高效查找仔细处理去重逻辑