寻找数组中所有唯一的三元组,使其和为零。

huangapple go评论152阅读模式
英文:

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&lt;List&lt;Integer&gt;&gt; threeSum(int[] nums) {
        //Arrays.sort(nums);
        int isZero = 0;
        
        for(int i = 0; i &lt; nums.length; i++)
        {
            for(int j = i+1; j&lt; nums.length; j++)
            {
                for(int x = i + 2; x &lt; 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&lt;List&lt;Integer&gt;&gt; threeSum(int[] nums) {
    int isZero = 0;
    List&lt;List&lt;Integer&gt;&gt; result = new ArrayList&lt;&gt;();

    for(int i = 0; i &lt; nums.length; i++){
        for(int j = i+1; j&lt; nums.length; j++){
            for(int x = i + 2; x &lt; 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&lt;List&lt;Integer&gt;&gt; threeSum(int[] nums) {
    Set&lt;List&lt;Integer&gt;&gt; result = new HashSet&lt;&gt;();
    int isZero = 0;
    for (int i = 0; i &lt; nums.length - 2; i++) {
        for (int j = i + 1; j &lt; nums.length - 1; j++) {
            for (int x = i + 2; x &lt; nums.length; x++) {
                if (nums[i] + nums[j] + nums[x] == isZero) {
                    List&lt;Integer&gt; 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&lt;List&lt;Integer&gt;&gt; threeSum(int[] A) {
    
 if ( A.length &lt;= 2 ) return List.of();
	
	Set&lt;List&lt;Integer&gt;&gt; set = new HashSet&lt;&gt;();
	
	for (int i = 0; i &lt; A.length; ++i) {
		
		for (int j = i + 1; j &lt; A.length ; ++j) {
			int thirdNumber = - ( A[i] + A[j] ) ;
			List&lt;Integer&gt; 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&lt;Integer&gt; temp = Arrays.asList(A[i], A[j], thirdNumber);
				Collections.sort(temp);
				set.add(temp);
			}				
		}
	}
	
	return new ArrayList&lt;&gt;(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&lt;List&lt;Integer&gt;&gt; threeSum(int[] nums) {
    Arrays.sort(nums);  // Sort the array
    for (int i = 0; i &lt; nums.length; i++) {
      for (int j = i + 1; j &lt; nums.length; j++) {
        for (int x = j + 1; x &lt; nums.length; x++) {
          if (nums[i] + nums[j] + nums[x] == 0) {
            res.add(Arrays.asList(nums[i], nums[j], nums[x]));
          }
        }
      }
    }
    return res;
  }

huangapple
  • 本文由 发表于 2020年8月26日 03:58:35
  • 转载请务必保留本文链接:https://go.coder-hub.com/63586245.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定