企业官网建设流程全解析

wordpress网站更改不见,意大利设计网站,广西省河池建设局网站,网站开发与管理实验五哈喽各位#xff0c;我是前端小L。 场景想象#xff1a; 给你一个数组 [-1, 0, 1, 2, -1, -4]。 我们要找出所有和为 0 的三个数 [a, b, c]。 我们可以找到 [-1, 0, 1]。 还可以找到 [-1, 2, -1]#xff08;排序后是 [-1, -1, 2]#xff09;。 难点#xff1a;数组里…哈喽各位我是前端小L。场景想象给你一个数组 [-1, 0, 1, 2, -1, -4]。我们要找出所有和为 0 的三个数 [a, b, c]。我们可以找到[-1, 0, 1]。还可以找到[-1, 2, -1]排序后是[-1, -1, 2]。难点数组里有两个-1如果我们不加控制代码很可能会把第一个-1开头的[-1, 0, 1]算一次再把第二个-1开头的[-1, 0, 1]又算一次。这就是重复。力扣 15. 三数之和https://leetcode.cn/problems/3sum/题目分析输入整数数组nums。输出所有和为 0 的不重复三元组。复杂度要求暴力法是 $O(N^3)$肯定超时。我们需要优化到$O(N^2)$。核心思维排序 固定一个找另外两个既然双指针擅长解决“两数之和”那我们能不能把“三数之和”降维打击策略先排序这是去重和使用双指针的前提(例如[-4, -1, -1, 0, 1, 2])。遍历固定位 (i)我们遍历数组固定第一个数nums[i]。双指针找两数剩下的问题就变成了——“在i后面的数组中找到两个数Left和Right使得nums[Left] nums[Right] -nums[i]”。去重逻辑最关键外层去重针对 i如果 nums[i] nums[i-1]说明这个数刚才已经作为“第一个数”处理过了再处理一遍肯定会得到一样的结果。跳过内层去重针对 Left 和 Right当我们找到了一个合法的组合后如果 nums[Left] nums[Left1]说明下一个数还是一样会导致结果重复。跳过 右边同理。算法流程 (JavaScript)排序nums.sort((a, b) a - b)。外层循环i从0到n-2。如果nums[i] 0因为已经排序第一个数大于0后面不可能凑出 0 了直接break。去重if (i 0 nums[i] nums[i - 1]) continue;双指针启动L i 1,R n - 1。计算sum nums[i] nums[L] nums[R]。sum 0数太大了R往左移。sum 0数太小了L往右移。sum 0记录答案res.push([nums[i], nums[L], nums[R]])。内层去重while (L R nums[L] nums[L1]) L;(跳过重复的L)内层去重while (L R nums[R] nums[R-1]) R--;(跳过重复的R)双双移动L,R--(寻找下一组)。代码实现JavaScript/** * param {number[]} nums * return {number[][]} */ var threeSum function(nums) { const result []; // 1. 必须排序 nums.sort((a, b) a - b); const len nums.length; for (let i 0; i len; i) { // 剪枝如果第一个数已经大于0后面都是正数不可能凑成0 if (nums[i] 0) break; // 2. 外层去重如果我们遇到了和上一次一样的数字跳过 // 注意是 i 0防止 i-1 越界 if (i 0 nums[i] nums[i - 1]) continue; let L i 1; let R len - 1; while (L R) { const sum nums[i] nums[L] nums[R]; if (sum 0) { // 找到一组加入结果 result.push([nums[i], nums[L], nums[R]]); // 3. 内层去重找到答案后看看左右指针旁边是不是有重复的 // 如果有一直跳过直到指向最后一个重复元素的下一位 while (L R nums[L] nums[L 1]) L; while (L R nums[R] nums[R - 1]) R--; // 找到答案后两个指针都要收缩 L; R--; } else if (sum 0) { // 和太小左指针右移变大 L; } else { // sum 0 // 和太大右指针左移变小 R--; } } } return result; };深度辨析为什么去重是nums[i] nums[i-1]很多同学会纠结是判断nums[i] nums[i-1]还是nums[i] nums[i1]情况 A (nums[i] nums[i-1])比如 [-1, -1, 2]。i0(第一个 -1)处理一遍找到了[-1, -1, 2]。i1(第二个 -1)我们回头看发现前一个也是 -1。如果我们再处理就会重复寻找。所以跳过。这是正确的逻辑只要我前面那个“长得跟我一样”的兄弟已经处理过了我就不用再处理了。情况 B (nums[i] nums[i1])如果我们判断的是后一个。i0(第一个 -1)发现后面也是 -1直接跳过错这样你就漏掉了[-1, -1, 2]这一组情况这组情况需要用到两个 -1。结论我们去重的是“作为第一个加数的重复”而不是禁止三元组内部有重复数字。总结这道题是双指针的里程碑。掌握了它你就掌握了 “排序 降维 双指针夹逼 细致去重” 的完整套路。下一题预告四数之和如果面试官觉得三数之和太简单可能会随手丢给你一道LC 18. 四数之和。题目找到a b c d target。思路套娃。三数之和是固定i算两数之和。四数之和是固定k再固定i算两数之和。难点多了一层循环也就多了一层剪枝和去重的逻辑。准备好再加一层循环了吗下期见