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

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

Find all unique triplets in the array which gives the sum of zero

问题

这是我目前的代码：

  1. class Solution {
  2.     public List<List<Integer>> threeSum(int[] nums) {
  3.         //Arrays.sort(nums);
  4.         int isZero = 0;
  5.         
  6.         for(int i = 0; i < nums.length; i++)
  7.         {
  8.             for(int j = i+1; j< nums.length; j++)
  9.             {
  10.                 for(int x = i + 2; x < nums.length;x++ )
  11.                 {
  12.                     if(nums[i] + nums[j]+ nums[x] == isZero)
  13.                     {
  14.                         
  15.                        
  16.                     }
  17.                 }
  18.             }
  19.         }
  20.         return Collections.emptyList();
  21.         
  22.     }
  23. }

如有需要，您可以继续完善这段代码，尤其是在满足条件时的处理部分。如果有其他问题或需要进一步帮助，请随时提问。

英文:

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:

  1. //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.
  3. //Note:
  5. //The solution set must not contain duplicate triplets.
  7. //Example:
  9. //Given array nums = [-1, 0, 1, 2, -1, -4],
  11. //A solution set is:
  12. //[
  13. //  [-1, 0, 1],
  14. //  [-1, -1, 2]
  15. //]

and this is what I have so far

  2. class Solution {
  3.     public List&lt;List&lt;Integer&gt;&gt; threeSum(int[] nums) {
  4.         //Arrays.sort(nums);
  5.         int isZero = 0;
  6.         
  7.         for(int i = 0; i &lt; nums.length; i++)
  8.         {
  9.             for(int j = i+1; j&lt; nums.length; j++)
  10.             {
  11.                 for(int x = i + 2; x &lt; nums.length;x++ )
  12.                 {
  13.                     if(nums[i] + nums[j]+ nums[x] == isZero)
  14.                     {
  15.                         
  16.                        
  17.                     }
  18.                 }
  19.             }
  20.         }
  21.         return Collections.emptyList();
  22.         
  23.     }
  24. }

答案1

得分: 1

以下是翻译好的内容：

需要一个外部的 List 来存储数组，并且在每次匹配时保存这三个值。

  1. public List<List<Integer>> threeSum(int[] nums) {
  2.     int isZero = 0;
  3.     List<List<Integer>> result = new ArrayList<>();
  5.     for(int i = 0; i < nums.length; i++){
  6.         for(int j = i+1; j< nums.length; j++){
  7.             for(int x = i + 2; x < nums.length;x++ ){
  8.                 if(nums[i] + nums[j]+ nums[x] == isZero){
  9.                     result.add(Arrays.asList(nums[i], nums[j], nums[x]));
  10.                 }
  11.             }
  12.         }
  13.     }
  14.     return result;        
  15. }

如果你的意思是要对三元组进行排序，并且避免重复，

  • 使用一个 Set
  • 在添加到内部列表之前对内部列表进行排序
  • 你可以通过在前两个循环的末尾边界上使用 -2 和 -1 来去除无用的迭代。
  1. public static Set<List<Integer>> threeSum(int[] nums) {
  2.     Set<List<Integer>> result = new HashSet<>();
  3.     int isZero = 0;
  4.     for (int i = 0; i < nums.length - 2; i++) {
  5.         for (int j = i + 1; j < nums.length - 1; j++) {
  6.             for (int x = i + 2; x < nums.length; x++) {
  7.                 if (nums[i] + nums[j] + nums[x] == isZero) {
  8.                     List<Integer> tmp = Arrays.asList(nums[i], nums[j], nums[x]);
  9.                     tmp.sort(Comparator.naturalOrder());
  10.                     result.add(tmp);
  11.                 }
  12.             }
  13.         }
  14.     }
  15.     return result;
  16. }
英文:

You need an outer List to store the arrays, and at each match save the 3 values

  1. public List&lt;List&lt;Integer&gt;&gt; threeSum(int[] nums) {
  2.     int isZero = 0;
  3.     List&lt;List&lt;Integer&gt;&gt; result = new ArrayList&lt;&gt;();
  5.     for(int i = 0; i &lt; nums.length; i++){
  6.         for(int j = i+1; j&lt; nums.length; j++){
  7.             for(int x = i + 2; x &lt; nums.length;x++ ){
  8.                 if(nums[i] + nums[j]+ nums[x] == isZero){
  9.                     result.add(Arrays.asList(nums[i], nums[j], nums[x]));
  10.                 }
  11.             }
  12.         }
  13.     }
  14.     return result;        
  15. }

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

<!-- -->

  1. public static Set&lt;List&lt;Integer&gt;&gt; threeSum(int[] nums) {
  2.     Set&lt;List&lt;Integer&gt;&gt; result = new HashSet&lt;&gt;();
  3.     int isZero = 0;
  4.     for (int i = 0; i &lt; nums.length - 2; i++) {
  5.         for (int j = i + 1; j &lt; nums.length - 1; j++) {
  6.             for (int x = i + 2; x &lt; nums.length; x++) {
  7.                 if (nums[i] + nums[j] + nums[x] == isZero) {
  8.                     List&lt;Integer&gt; tmp = Arrays.asList(nums[i], nums[j], nums[x]);
  9.                     tmp.sort(Comparator.naturalOrder());
  10.                     result.add(tmp);
  11.                 }
  12.             }
  13.         }
  14.     }
  15.     return result;
  16. }

答案2

得分: 1

下面的代码通过了所有的测试。唯一的问题是时间复杂度为O(n*2)，在输入非常大的情况下会超时。如果有人改进算法，欢迎分享。

  1. class Solution {
  2.     public List<List<Integer>> threeSum(int[] A) {
  3.         
  4.      if (A.length <= 2) return List.of();
  5. 		
  6. 		Set<List<Integer>> set = new HashSet<>();
  7. 		
  8. 		for (int i = 0; i < A.length; ++i) {
  9. 			
  10. 			for (int j = i + 1; j < A.length; ++j) {
  11. 				int thirdNumber = - (A[i] + A[j]);
  12. 				List<Integer> tempp = Arrays.stream(A).boxed().collect(Collectors.toList());
  13. 				tempp.remove(Integer.valueOf(A[i]));
  14. 				tempp.remove(Integer.valueOf(A[j]));
  15. 				if (tempp.contains(Integer.valueOf(thirdNumber))) {
  16. 					List<Integer> temp = Arrays.asList(A[i], A[j], thirdNumber);
  17. 					Collections.sort(temp);
  18. 					set.add(temp);
  19. 				}				
  20. 			}
  21. 		}
  22. 		
  23. 		return new ArrayList<>(set);
  24.     }
  25. }
英文:

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.

  1. class Solution {
  2. public List&lt;List&lt;Integer&gt;&gt; threeSum(int[] A) {
  3.     
  4.  if ( A.length &lt;= 2 ) return List.of();
  5. 	
  6. 	Set&lt;List&lt;Integer&gt;&gt; set = new HashSet&lt;&gt;();
  7. 	
  8. 	for (int i = 0; i &lt; A.length; ++i) {
  9. 		
  10. 		for (int j = i + 1; j &lt; A.length ; ++j) {
  11. 			int thirdNumber = - ( A[i] + A[j] ) ;
  12. 			List&lt;Integer&gt; tempp = Arrays.stream(A).boxed().collect(Collectors.toList());
  13. 			tempp.remove(Integer.valueOf(A[i]));
  14. 			tempp.remove(Integer.valueOf(A[j]));
  15. 			if (tempp.contains(Integer.valueOf(thirdNumber))) {
  16. 				List&lt;Integer&gt; temp = Arrays.asList(A[i], A[j], thirdNumber);
  17. 				Collections.sort(temp);
  18. 				set.add(temp);
  19. 			}				
  20. 		}
  21. 	}
  22. 	
  23. 	return new ArrayList&lt;&gt;(set);
  24. }

}

答案3

得分: 0

你可以在收集三元组之前对数组进行排序，这样这些三元组也会被排序。

  1. public Set<List<Integer>> threeSum(int[] nums) {
  2.   Arrays.sort(nums);  // 对数组进行排序
  3.   for (int i = 0; i < nums.length; i++) {
  4.     for (int j = i + 1; j < nums.length; j++) {
  5.       for (int x = j + 1; x < nums.length; x++) {
  6.         if (nums[i] + nums[j] + nums[x] == 0) {
  7.           res.add(Arrays.asList(nums[i], nums[j], nums[x]));
  8.         }
  9.       }
  10.     }
  11.   }
  12.   return res;
  13. }
英文:

You can sort the array before collecting those triplets, then those triplets are also sorted.

  1.   public Set&lt;List&lt;Integer&gt;&gt; threeSum(int[] nums) {
  2.     Arrays.sort(nums);  // Sort the array
  3.     for (int i = 0; i &lt; nums.length; i++) {
  4.       for (int j = i + 1; j &lt; nums.length; j++) {
  5.         for (int x = j + 1; x &lt; nums.length; x++) {
  6.           if (nums[i] + nums[j] + nums[x] == 0) {
  7.             res.add(Arrays.asList(nums[i], nums[j], nums[x]));
  8.           }
  9.         }
  10.       }
  11.     }
  12.     return res;
  13.   }

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

发表评论

匿名网友

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

确定