题目描述
链接
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
思路
- 回溯法(提交超时)
1.1 0-1背包思路
- 类似 0-1 背包问题，在 n 个整数中选择 3 个数，3 个数的和为 0。
- 一个元素占树的一层，按深度优先遍历树，边为 0 表示不选这个数，边为1 表示选这个数。
- 回溯搜索过程，当过程集中当前整数个数等于 3 且和当前和等于 0，则把过程集加入结果集中。
-
对于去重处理，用到排序+LinkedHashSet，其中LinkedHashSet是有序的
假设输入：nums = [-1,0,1,2]，过程如图：
image.png
Java 代码如下：
class Solution {
LinkedHashSet<List<Integer>> result = new LinkedHashSet<>();
List<Integer> way = new ArrayList<>();
public List<List<Integer>> threeSum(int[] nums) {
if (nums.length < 3) {
return new ArrayList<>();
}
Arrays.sort(nums);
int num = 3;
int sum = 0;
//当前数量
int currentNum = 0;
//当前和
int currentSum = 0;
backTrack(nums, num, sum, 0, nums.length, currentNum, currentSum);
return new ArrayList<>(result);
}
public void backTrack(int[] nums, int num, int sum, int t, int len, int currentNum, int currentSum) {
if (t > len - 1 || currentNum >= num) {
if (currentNum == num && currentSum == sum) {
List temp = new ArrayList(way);
result.add(temp);
}
return ;
}
if (currentSum > 0 && nums[t] >= 0) {
return;
}
if ((currentNum + 1) <= num) {
++currentNum;
currentSum += nums[t];
way.add(nums[t]);
backTrack(nums, num, sum, t + 1, len, currentNum, currentSum);
--currentNum;
currentSum -= nums[t];
way.remove(way.size() - 1);
}
backTrack(nums, num, sum, t + 1, len, currentNum, currentSum);
}
}
1.2 选择回溯思路
-
回溯法还一种写法是从剩下的元素中选择一个加到过程集，相比1.1 中，遍历层数更少，性能更优。
假设输入：nums = [-1,0,1,2,-1,4],过程如图：
image.png
Java 代码如下：
public static void backTrack(int[] nums, int t, int target) {
if (way.size() == 3) {
if (way.get(0) + way.get(1) + way.get(2) == target) {
if (!result.contains(way)) {
List temp = new ArrayList(way);
Collections.sort(temp);
result.add(temp);
}
}
return;
}
for (int i = t; i < nums.length; i++) {
if(nums.length-i < 3-way.size()){
return;
}
way.add(nums[i]);
backTrack(nums, i + 1, target);
way.remove(way.size() - 1);
}
}
- 三指针法
- 首先对数组排序
- 选择一个数 nums[j],再用左右指针指向 nums[j]后面的两端。
- 计算三个数和。当和等于 0时，则将三个数加入结果集，此时，如果左指针当前值与下一个值相等，则跳过，即 l++,如果右指针当前值与下一个值相等，则跳过，即 r++；当和大于 0 时，需要往左边小的数字寻找答案，右指针往左走；当和小于 0 时，需要往右边大的数字寻找答案，左指针往右走。
- j也要跳过重复元素。
Java 代码如下：
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList();
if(nums.length == 0){
return result;
}
Arrays.sort(nums);
for(int j = 0;j < nums.length;j++){
int l = j+1;
int r = nums.length-1;
// System.out.println("j"+nums[j]);
while(l < r){
// System.out.println("j"+nums[j]);
// System.out.println("l"+nums[l]);
// System.out.println("r"+nums[r]);
int sum = nums[j]+nums[l]+nums[r];
// System.out.println("sum"+sum);
if(sum == 0){
List<Integer> way = new ArrayList<Integer>();
way.add(nums[j]);
way.add(nums[l]);
way.add(nums[r]);
result.add(way);
while((l+1) < nums.length && nums[l] == nums[l+1]){
l++;
}
l++;
while((r-1) >=0 && nums[r] == nums[r-1]){
r--;
}
r--;
}else if(sum > 0){
while((r-1) >=0 && nums[r] == nums[r-1]){
r--;
}
r--;
}else{
while((l+1) < nums.length && nums[l] == nums[l+1]){
l++;
}
l++;
}
}
while((j+1) < nums.length && nums[j] == nums[j+1]){
j++;
}
}
return result;
}
}
C++代码如下：
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
if(nums.size() == 0){
return result;
}
sort(nums.begin(),nums.end());
for(int j = 0;j<nums.size();j++){
int l = j+1;
int r = nums.size()-1;
while(l<r){
int sum = nums[j]+nums[l]+nums[r];
if(sum == 0){
vector<int> way;
way.push_back(nums[j]);
way.push_back(nums[l]);
way.push_back(nums[r]);
result.push_back(way);
while((l+1) < nums.size() && nums[l] == nums[l+1]){
l++;
}
l++;
while((r-1) >= 0 && nums[r] == nums[r-1]){
r--;
}
r--;
}else if(sum > 0){
while((r-1) >= 0 && nums[r] == nums[r-1]){
r--;
}
r--;
}else{
while((l+1) < nums.size() && nums[l] == nums[l+1]){
l++;
}
l++;
}
while((j+1) < nums.size() && nums[j] == nums[j+1]){
j++;
}
}
}
return result;
}
};
遇到的问题
- 去重处理
- 回溯法中的去重主要用到排序+LinkedHashSet，LinkedHashSet是Set集合的一个实现，继承自HashSet，内部使用的是LinkHashMap。具有set集合不重复的特点，同时是有序的，是一个非线程安全的集合。HashSet继承自AbstractSet，实现了Set接口，内部使用HashMap来存储数据，数据存储在HashMap的key中，value都是同一个默认值。
- 三指针法中的去重主要是排序+判断值相等则继续移动
- Java 中数组和链表排序的方法区分
- Arrays中的sort()方法主要是针对各种数据类型（基本数据类型和引用对象类型）的数组元素排序。
- java.util.Collections中的静态方法的Collection.sort()主要是针对集合框架中的动态数组，链表，树，哈希表等（ ArrayList、LinkedList、HashSet、LinkedHashSet、HashMap、LinkedHashMap ）进行排序。
