三数之和
肝算法第一天 给👴🏻冲
题目#
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。注意：答案中不可以包含重复的三元组。
// eg: list: [-1, 1, -2, 0] target: 0// 输出: [-1, 0, 1]思路#
可仿照两数之和暴力三层遍历，最后去重处理，但无意义
-
指针查数
选取一个数固定住(例如第一个),选择第二个和最后一个数，作为指针
leftright, left++ 和 right—，不断循环找到结果 -
数组排序
原数组排序后，更适合双指针确定范围并查询
const list = [-2, -1, 0, 1, 2];const target = 0;/**-2 | -1 2 (-1 + 2 小于 0 - -2， 所以 left 指针++)-2 | 0 2 返回 [-2, 0, 2]-1 | 0 2 (0 + 2 大于 0 - -1， 所以 right -- )-1 | 0 1 返回 [-1, 0, 1]0 | 1 2 到头了弟弟*/
如此思路开始构造函数
function sumThreeNum(list, target) { const sl = list.sort((a, b) => a - b); const res = [];
for (let i = 0, len = list.length; i < len; i++) { const curr = sl[i]; const st = target - curr; // st subTarget let l = i + 1; let r = len - 1;
// 因为是排序后的数组，所以后面必然比目标大 if (curr > target) break;
// 避免当前固定数 与上次固定数一样 if (i === 0 || sl[i - 1] !== curr) { while (l < r) { /** 核心逻辑 若左右之和等于子目标 则输出 若左右之和小于子目标 则 left 指针进一位 若左右之和大于子目标 则 right 指针减一位 靠指针缩进范围查询 */ if (sl[l] + sl[r] === st) { res.push([sl[i], sl[l], sl[r]]);
// 避免下个指针数值和当前数值一样 while (l < r && sl[l + 1] === sl[l]) l++; while (l < r && sl[r - 1] === sl[r]) r--;
l++; r--; } else if (sl[l] + sl[r] < target) { l++; } else { r--; } } } }
return res;}要记住双指针的解法
