问题：

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: 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]]

解决：

① 首先想到暴力破解，O(n^3)的时间复杂度，必然超时。

② 数组排序+双指针 O(n^2) --- 动态规划

第一步，对数组排序。

第二步， 分析1：对于元素 S[i] ， 最后的答案可以分为两种，包含 S[i] 的，和不包含 S[i] 的。当包含 S[i] 的情况都找到后，后续就可以不用再考虑 S[i] 。 分析2：对于 S[i] ， l = i+1, r = len-1 。若 s[i] + S[l] + S[r] == 0， 则为原问题的一个解。 当 S[i] + S[l] > -S[r] 时，则 r-- 当 S[i] + S[l] < -S[r] 时，则 l++ 当 S[i] + S[i] = -S[r] 时， 表示是原问题的一个解，则 l++, r--; 第三步，性能优化。同样根据分析1，若 S[i] == S[i+1]，可以跳过。

class Solution { //72ms

    List<List<Integer>> res = new ArrayList<>();     public List<List<Integer>> threeSum(int[] nums) {         if(nums == null || nums.length < 3) return res;         Arrays.sort(nums);         int len = nums.length;         for (int i = 0;i < len - 2 ;i ++ ) {             if(i > 0 && nums[i] == nums[i - 1]) continue;             twoSum(nums,i + 1,len - 1,nums[i]);         }         return res;     }     public void twoSum(int[] nums,int begin,int end,int sum1){         while(begin < end){             if(nums[begin] + nums[end] + sum1== 0){                 List<Integer> tmp = new ArrayList<>();                 tmp.add(sum1);                 tmp.add(nums[begin]);                 tmp.add(nums[end]);                 res.add(tmp);                 while(begin < end && nums[begin] == nums[begin + 1]) begin ++;

                while(begin < end && nums[end] == nums[end - 1]) end --;                 begin ++;                 end --;             }else if(nums[begin] + nums[end] + sum1< 0){                 begin ++;             }else{                 end --;             }         }     } }

② 这样写简单点

class Solution { //81ms

    List<List<Integer>> res = new ArrayList<>();     public List<List<Integer>> threeSum(int[] nums) {         if(nums == null || nums.length < 3) return res;         Arrays.sort(nums);         int len = nums.length;         for (int i = 0;i < len - 2 ;i ++ ) {             if(i > 0 && nums[i] == nums[i - 1]) continue;             twoSum(nums,i + 1,len - 1,nums[i]);         }         return res;     }     public void twoSum(int[] nums,int begin,int end,int sum1){         while(begin < end){             if(nums[begin] + nums[end] + sum1== 0){                 res.add(Arrays.asList(sum1,nums[begin],nums[end]));                 while(++ begin < end && nums[begin] == nums[begin - 1]);                 while(-- end > begin && nums[end] == nums[end + 1]);             }else if(nums[begin] + nums[end] + sum1< 0){                 begin ++;             }else{                 end --;             }         }     } }