Contents

1. 1. 题意：
2. 2. 分析：

/*

• 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, 不允许重复。

分析：

先排序，再左右夹逼，复杂度 O(n*n)。
N-sum 的题目都可以用夹逼做，复杂度可以降一维。   

class Solution {  
   public:  
       vector<vector<int> > threeSum(vector<int> &num) {  
           vector<vector<int> > ret;  
           int len = num.size();  
           int tar = 0;  
     
           if (len <= 2)  
               return ret;  
     
           sort(num.begin(), num.end());  
     
           for (int i = 0; i <= len - 3; i++) {  
               // first number : num[i]  
               int j = i + 1;  // second number  
               int k = len - 1;    // third number  
               while (j < k) {  
                   if (num[i] + num[j] + num[k] < tar) {  
                       ++j;  
                   } else if (num[i] + num[j] + num[k] > tar) {  
                       --k;  
                   } else {  
                       ret.push_back({ num[i], num[j], num[k] });  
                       ++j;  
                       --k;  
                       // folowing 3 while can avoid the duplications  
                       while (j < k && num[j] == num[j - 1])  
                           ++j;  
                       while (j < k && num[k] == num[k + 1])  
                           --k;  
                   }  
               }  
               while (i <= len - 3 && num[i] == num[i + 1])  
                   ++i;  
           }   
           return ret;  
       }  
   };

import java.util.*;

public class ThreeSum {

    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        Arrays.sort(num);
        for (int i = 0; i < num.length - 2 && num[i] <= 0; i++) {
            if (i > 0 && num[i] == num[i - 1])
                continue;
            int j = i + 1;
            int k = num.length - 1;
            while (j < k) {
                if (num[i] + num[j] + num[k] > 0) {
                    k--;
                } else if (num[i] + num[j] + num[k] < 0) {
                    j++;
                } else {
                    ArrayList<Integer> list = new ArrayList<Integer>();
                    list.add(num[i]);
                    list.add(num[j]);
                    list.add(num[k]);
                    res.add(list);
                    do {
                        j++;
                    } while (j < k && num[j] == num[j - 1]);
                    do {
                        k--;
                    } while (j < k && num[k] == num[k + 1]);
                }
            }
        }
        return res;
    }

}