三数之和：回溯通过排序去重解法
🚀 三数之和（Three Sum）回溯解法深度解析
1️⃣ 问题背景
三数之和是经典的数组与回溯算法问题，核心目标是在整数数组中找到所有不重复的三元组，使其和为 0。
该问题在面试中常用于考察：搜索能力 + 去重逻辑 + 剪枝优化，属于典型中高频算法题。
2️⃣ 核心原理
本题采用 DFS 回溯思想，从数组中枚举所有可能的三元组合，并在叶子节点判断是否满足 sum = 0。
3️⃣ 数据结构分析
path：当前选择路径
result：最终结果集合
path 用于保存当前递归路径，当长度达到 3 时进行合法性判断。
4️⃣ 算法代码实现
完整 Java 实现如下：
public List
List
List
Arrays.sort(nums);
dfs(result, nums, path, 0);
return result;
}
public void dfs(List
if (path.size() == 3) {
if (path.get(0) + path.get(1) + path.get(2) == 0) {
result.add(new ArrayList<>(path));
}
return;
}
for (int i = start; i < nums.length; i++) {
if (i > start && nums[i] == nums[i - 1]) {
continue;
}
path.add(nums[i]);
dfs(result, nums, path, i + 1);
path.remove(path.size() - 1);
}
}
}
5️⃣ 执行流程
2. 从 index=0 开始 DFS
3. 逐个选择元素加入 path
4. path.size == 3 时判断 sum
5. 满足条件加入 result
6. 回溯撤销选择
7. 遍历所有组合
6️⃣ 实际案例
排序：[-4, -1, -1, 0, 1, 2]
输出：
[-1, -1, 2]
[-1, 0, 1]
7️⃣ 优缺点分析
- ✅ 思路清晰，适合理解组合搜索
- ✅ 可扩展为 kSum 问题
- ❌ 时间复杂度 O(n³)
- ❌ 存在大量无效搜索
8️⃣ 面试常见问题
- 为什么要排序？
- 如何去重？
- 回溯和双指针区别？
- 如何优化时间复杂度？
核心考察点：去重逻辑 + 搜索剪枝 + 优化思维
9️⃣ 总结
相关文章
-
JVM创建对象的内存是如何分配的？如何保证线程安全？
Java对象默认在堆中分配内存。当多个线程同时创建对象时，JVM通过CAS、自旋重试、本地线程分配缓冲区（TLAB）等机制保证内存分配过程的线程安全。对象创建过程涉及类加载检查、内存分配、零值初始化、对象头设置以及构造方法执行等多个步骤，是JVM面试中的高频考点。
NEW个对象 2026-06-09
-
数据库出现死锁的案例
报告生成案例： 报告编辑的时候：更新模板内容，更新报告引用的id。 报告生成的时候：更新报告引用的id，再更新模板内容。
NEW个对象 2025-08-01
-
JVM对象内存分配在哪里？从堆内存到栈上分配全面解析
JVM对象内存分配在哪里？从堆内存到栈上分配全面解析
NEW个对象 2026-06-10
