3Sum

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

• Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
• The solution set must not contain duplicate triplets.

For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2)

      

找到和為0的三個數字組合：

先排序，定點從左到右走。每一個定點隻考慮它右邊的數字。右邊收縮尋找。

結果要求從小到大排好數字

1 package com.rust.cal;
 2 
 3 import java.util.ArrayList;
 4 import java.util.Arrays;
 5 import java.util.List;
 6 
 7 public class ThreeSum {
 8     /**
 9      * @param nums-int[]
10      * @return List<List<Integer>>
11      */
12     public static List<List<Integer>> threeSum(int[] nums) {
13         List<List<Integer>> res = new ArrayList<List<Integer>>();
14         if (nums.length < 3) {
15             return res;
16         }
17         Arrays.sort(nums);
18         int len = nums.length;
19         for (int i = 0; i < len - 2; i++) {
20             if (i > 0 && nums[i] == nums[i-1]) continue;//skip this loop
21             int l = i + 1;
22             int r = len - 1;
23             while (l < r) {
24                 List<Integer> singleAns = new ArrayList<Integer>();
25                 int sum = nums[l] + nums[r] + nums[i];
26                 if (sum == 0) {
27                     singleAns.add(nums[i]);
28                     singleAns.add(nums[l]);
29                     singleAns.add(nums[r]);
30                     res.add(singleAns);
31                     while (l < r && nums[l] == nums[l+1]) l++;  //look forward
32                     while (l < r && nums[r] == nums[r-1]) r--;   //skip the same number in nums[]
33                     l++;
34                     r--;
35                 } else if (sum > 0) {
36                     r--;
37                 } else {
38                     l++;
39                 }
40             }
41         }
42         return res;
43     }
44     public static void main(String args[]){
45         int[] nums = {1,2,-10,2,2,0,3,5,5,-5,-6,0};
46         List<List<Integer>> res = new ArrayList<List<Integer>>();
47         res = threeSum(nums);
48         System.out.println("All " + res.size());
49         for (int i = 0; i < res.size(); i++) {
50             for (int j = 0; j < res.get(i).size(); j++) {
51                 System.out.print(res.get(i).get(j) + "\t");
52             }
53             System.out.println();
54         }
55     }
56 }      

輸出：

All 4

-10 5 5

-6 1 5

-5 0 5

-5 2 3