题目描述
给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 。找出所有满足条件且不重复的三元组。
注意:答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4],
满足要求的三元组集合为: [ [-1, 0, 1], [-1, -1, 2] ]
总结
剪枝,left和right
Sample Code
class Solution {
public List
<List
<Integer>> threeSum(int[] nums
) {
List
<List
<Integer>> result
= new ArrayList<>();
if (nums
== null
|| nums
.length
== 0) return result
;
Arrays
.sort(nums
);
for (int k
= 0; k
< nums
.length
; k
++) {
if (nums
[k
] > 0) break;
if (k
> 0 && nums
[k
] == nums
[k
- 1]) continue;
int target
= 0 - nums
[k
];
int i
= k
+ 1;
int j
= nums
.length
- 1;
while (i
< j
) {
if (nums
[i
] + nums
[j
] == target
) {
List
<Integer> r
= new ArrayList<>();
r
.add(nums
[k
]);
r
.add(nums
[i
]);
r
.add(nums
[j
]);
result
.add(r
);
while (i
< j
&& nums
[i
] == nums
[i
+ 1]) ++i
;
while (i
< j
&& nums
[j
] == nums
[j
- 1]) --j
;
++i
;
--j
;
} else if (nums
[i
] + nums
[j
] < target
) ++i
;
else --j
;
}
}
return result
;
}
}
ERROR Code
class Solution {
public List
<List
<Integer>> threeSum(int[] nums
) {
Arrays
.sort(nums
);
List
<List
<Integer>> res
= new ArrayList<>();
find(0, new ArrayList<>(), 0, res
, nums
);
return res
;
}
private void find(int sum
, List
<Integer> list
, int start
, List
<List
<Integer>> res
, int[] nums
) {
if(list
.size() == 3 && sum
== 0)
res
.add(new ArrayList<>(list
));
for(int i
= start
; i
< nums
.length
; i
++) {
if(i
> start
&& nums
[i
] == nums
[i
-1]) continue;
list
.add(nums
[i
]);
find(sum
+nums
[i
], list
, i
+1, res
, nums
);
list
.remove(list
.size()-1);
}
}
}
ERROR Code 2
class Solution {
public List
<List
<Integer>> threeSum(int[] nums
) {
if(nums
== null
|| nums
.length
< 3) return new ArrayList<>();
List
<List
<Integer>> res
= new ArrayList<>();
Arrays
.sort(nums
);
int len
= nums
.length
;
if(nums
[0] <= 0 && nums
[len
-1] >= 0) {
for(int i
= 0; i
< len
-2; ) {
if(nums
[i
] > 0) break;
int left
= i
+1;
int right
= len
-1;
do {
if(left
>= right
|| nums
[i
] * nums
[right
] > 0) break;
int temp
= nums
[i
] + nums
[left
] + nums
[right
];
if(temp
== 0) {
List
<Integer> list
= new ArrayList<>();
list
.add(nums
[i
]);
list
.add(nums
[left
]);
list
.add(nums
[right
]);
res
.add(list
);
}
if(temp
< 0)
while(left
< right
&& nums
[left
] == nums
[++left
]) {}
else
while(left
< right
&& nums
[right
] == nums
[--right
]) {}
}while(left
< right
);
while(i
< len
-1 && nums
[i
] == nums
[++i
]) {}
}
}
return res
;
}
}