目录1. 题目解析1.1 题目描述15. 三数之和示例 1手写图示解析2. 算法原理2.1 解法一排序 暴力枚举 利用 set 去重 —— O(n³)2.2 解法二排序 双指针 —— O(n²)步骤手写图示处理细节问题1. 去重2. 不漏优化点3. 编写代码总结OJ链接https://leetcode.cn/problems/3sum/description/1. 题目解析1.1 题目描述15. 三数之和难度中等给你一个整数数组nums判断是否存在三元组[nums[i], nums[j], nums[k]]满足i ! j、i ! k且j ! k同时还满足nums[i] nums[j] nums[k] 0。请你返回所有和为 0 且不重复的三元组。注意答案中不可以包含重复的三元组。示例 1输入nums [-1,0,1,2,-1,-4]输出[[-1,-1,2],[-1,0,1]]解释nums[0] nums[1] nums[2] (-1) 0 1 0。nums[1] nums[2] nums[4] 0 1 (-1) 0。nums[0] nums[3] nums[4] (-1) 2 (-1) 0。不同的三元组是[-1,0,1]和[-1,-1,2]。注意输出的顺序和三元组的顺序并不重要。手写图示解析原数组[-1, 0, 1, 2, -1, -4]→ 排序后[-4, -1, -1, 0, 1, 2]→ 尝试组合[-1, 0, 1]✔️[-1, 2, -1]✔️[0, 1, -1]×注对三元组[−1, 0, 1]和[−1, 2, −1]的判断以及[0, 1, −1]被划掉说明答案中不可包含重复的三元组即使数值相同顺序不同也视为重复。2. 算法原理2.1 解法一排序 暴力枚举 利用 set 去重 —— O(n³)思路先对数组排序然后用三重循环枚举所有可能的三元组将符合条件的存入Set中去重最后转为列表返回。手写图示排序后数组[-4, -1, -1, 0, 1, 2]→ 找到[-1, 0, 1]两次说明需要去重。→ 箭头指向O(n³)表示时间复杂度。缺点 时间复杂度高效率低下。2.2 解法二排序 双指针 —— O(n²)步骤排序将数组升序排列。固定一个数a即nums[i]。在该数后面的区间内利用“双指针算法”快速找到两个数的和等于-a即可。手写图示排序后数组[-4, -4, -1, 0, 0, 0, 1, 1, 4, 4, 5, 6]→ 固定i0值为-4left1right11目标值t4。→ 指针移动过程图示清晰。处理细节问题1. 去重找到一种结果之后left和right指针要跳过重复元素while(left right nums[left] nums[left - 1]) left; while(left right nums[right] nums[right 1]) right--;当使用完一次双指针算法之后i也需要跳过重复元素while(i n nums[i] nums[i - 1]) i;2. 不漏找到一种结果之后不要“停”缩小区间继续寻找。优化点固定数a 0因为数组已排序若a 0则后续所有数都大于0三数之和不可能为0可直接break。避免越界指针移动时需保证left right。3. 编写代码class Solution { // 时间复杂度 O(N^2) public ListListInteger threeSum(int[] nums) { ListListInteger ret new ArrayList(); // 1. 排序 Arrays.sort(nums); // 2. 利用双指针解决问题 int n nums.length; for(int i 0; i n; ) { if(nums[i] 0) break; // 小优化 int left i 1, right n - 1, target -nums[i]; while(left right) { int sum nums[left] nums[right]; if(sum target) right--; else if(sum target) left; else { // nums[i] nums[left] nums[right] ret.add(new ArrayListInteger(Arrays.asList(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--; } } // 去重: i i; while(i n nums[i] nums[i - 1]) i; } return ret; } }总结核心思想排序 双指针将 O(n³) 优化至 O(n²)。关键点排序是基础。固定一个数双指针找另外两个数。去重处理三个地方i,left,right都要跳过重复元素。小优化nums[i] 0时直接 break避免无效计算。易错点去重逻辑必须严格否则会包含重复三元组。
