英文:
Find all unique triplets in the array which gives the sum of zero
问题
这是我目前的代码:
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
//Arrays.sort(nums);
int isZero = 0;
for(int i = 0; i < nums.length; i++)
{
for(int j = i+1; j< nums.length; j++)
{
for(int x = i + 2; x < nums.length;x++ )
{
if(nums[i] + nums[j]+ nums[x] == isZero)
{
}
}
}
}
return Collections.emptyList();
}
}
如有需要,您可以继续完善这段代码,尤其是在满足条件时的处理部分。如果有其他问题或需要进一步帮助,请随时提问。
英文:
I am having a difficult time with this question. So I am trying to display the correct solutions in forms of strings but having a difficult time with the last for loop. Also is there a way to sort these arrays or just simply add the Arrays.sort function?
The questions follows:
//Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all //unique triplets in the array which gives the sum of zero.
//Note:
//The solution set must not contain duplicate triplets.
//Example:
//Given array nums = [-1, 0, 1, 2, -1, -4],
//A solution set is:
//[
// [-1, 0, 1],
// [-1, -1, 2]
//]
and this is what I have so far
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
//Arrays.sort(nums);
int isZero = 0;
for(int i = 0; i < nums.length; i++)
{
for(int j = i+1; j< nums.length; j++)
{
for(int x = i + 2; x < nums.length;x++ )
{
if(nums[i] + nums[j]+ nums[x] == isZero)
{
}
}
}
}
return Collections.emptyList();
}
}
答案1
得分: 1
以下是翻译好的内容:
需要一个外部的 List
来存储数组,并且在每次匹配时保存这三个值。
public List<List<Integer>> threeSum(int[] nums) {
int isZero = 0;
List<List<Integer>> result = new ArrayList<>();
for(int i = 0; i < nums.length; i++){
for(int j = i+1; j< nums.length; j++){
for(int x = i + 2; x < nums.length;x++ ){
if(nums[i] + nums[j]+ nums[x] == isZero){
result.add(Arrays.asList(nums[i], nums[j], nums[x]));
}
}
}
}
return result;
}
如果你的意思是要对三元组进行排序,并且避免重复,
- 使用一个
Set
- 在添加到内部列表之前对内部列表进行排序
- 你可以通过在前两个循环的末尾边界上使用
-2
和-1
来去除无用的迭代。
public static Set<List<Integer>> threeSum(int[] nums) {
Set<List<Integer>> result = new HashSet<>();
int isZero = 0;
for (int i = 0; i < nums.length - 2; i++) {
for (int j = i + 1; j < nums.length - 1; j++) {
for (int x = i + 2; x < nums.length; x++) {
if (nums[i] + nums[j] + nums[x] == isZero) {
List<Integer> tmp = Arrays.asList(nums[i], nums[j], nums[x]);
tmp.sort(Comparator.naturalOrder());
result.add(tmp);
}
}
}
}
return result;
}
英文:
You need an outer List
to store the arrays, and at each match save the 3 values
public List<List<Integer>> threeSum(int[] nums) {
int isZero = 0;
List<List<Integer>> result = new ArrayList<>();
for(int i = 0; i < nums.length; i++){
for(int j = i+1; j< nums.length; j++){
for(int x = i + 2; x < nums.length;x++ ){
if(nums[i] + nums[j]+ nums[x] == isZero){
result.add(Arrays.asList(nums[i], nums[j], nums[x]));
}
}
}
}
return result;
}
If you meant so sort the triplets, and so no have duplicate,
- use a
Set
- sort the inner list before
- you can remove useless iteration with
-2
and-1
on the end bound of the 2 first loops
<!-- -->
public static Set<List<Integer>> threeSum(int[] nums) {
Set<List<Integer>> result = new HashSet<>();
int isZero = 0;
for (int i = 0; i < nums.length - 2; i++) {
for (int j = i + 1; j < nums.length - 1; j++) {
for (int x = i + 2; x < nums.length; x++) {
if (nums[i] + nums[j] + nums[x] == isZero) {
List<Integer> tmp = Arrays.asList(nums[i], nums[j], nums[x]);
tmp.sort(Comparator.naturalOrder());
result.add(tmp);
}
}
}
}
return result;
}
答案2
得分: 1
下面的代码通过了所有的测试。唯一的问题是时间复杂度为O(n*2),在输入非常大的情况下会超时。如果有人改进算法,欢迎分享。
class Solution {
public List<List<Integer>> threeSum(int[] A) {
if (A.length <= 2) return List.of();
Set<List<Integer>> set = new HashSet<>();
for (int i = 0; i < A.length; ++i) {
for (int j = i + 1; j < A.length; ++j) {
int thirdNumber = - (A[i] + A[j]);
List<Integer> tempp = Arrays.stream(A).boxed().collect(Collectors.toList());
tempp.remove(Integer.valueOf(A[i]));
tempp.remove(Integer.valueOf(A[j]));
if (tempp.contains(Integer.valueOf(thirdNumber))) {
List<Integer> temp = Arrays.asList(A[i], A[j], thirdNumber);
Collections.sort(temp);
set.add(temp);
}
}
}
return new ArrayList<>(set);
}
}
英文:
The below code passes all tests. The only issue is the time complexity of O(n*2), where time exceeds for very LARGE inputs. Welcome, if someone improves the algorithm.
class Solution {
public List<List<Integer>> threeSum(int[] A) {
if ( A.length <= 2 ) return List.of();
Set<List<Integer>> set = new HashSet<>();
for (int i = 0; i < A.length; ++i) {
for (int j = i + 1; j < A.length ; ++j) {
int thirdNumber = - ( A[i] + A[j] ) ;
List<Integer> tempp = Arrays.stream(A).boxed().collect(Collectors.toList());
tempp.remove(Integer.valueOf(A[i]));
tempp.remove(Integer.valueOf(A[j]));
if (tempp.contains(Integer.valueOf(thirdNumber))) {
List<Integer> temp = Arrays.asList(A[i], A[j], thirdNumber);
Collections.sort(temp);
set.add(temp);
}
}
}
return new ArrayList<>(set);
}
}
答案3
得分: 0
你可以在收集三元组之前对数组进行排序,这样这些三元组也会被排序。
public Set<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums); // 对数组进行排序
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
for (int x = j + 1; x < nums.length; x++) {
if (nums[i] + nums[j] + nums[x] == 0) {
res.add(Arrays.asList(nums[i], nums[j], nums[x]));
}
}
}
}
return res;
}
英文:
You can sort the array before collecting those triplets, then those triplets are also sorted.
public Set<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums); // Sort the array
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
for (int x = j + 1; x < nums.length; x++) {
if (nums[i] + nums[j] + nums[x] == 0) {
res.add(Arrays.asList(nums[i], nums[j], nums[x]));
}
}
}
}
return res;
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论