三数之和

step 1：排除边界特殊情况。 step 2：既然三元组内部要求非降序排列，那我们先得把这个无序的数组搞有序了，使用sort函数优先对其排序。 step 3：得到有序数组后，遍历该数组，对于每个遍历到的元素假设它是三元组中最小的一个，那么另外两个一定在后面。 step 4：需要三个数相加为0，则另外两个数相加应该为上述第一个数的相反数，我们可以利用双指针在剩余的子数组中找有没有这样的数对。双指针指向剩余子数组的首尾，如果二者相加为目标值，那么可以记录，而且二者中间的数字相加可能还会有。 step 5：如果二者相加大于目标值，说明右指针太大了，那就将其左移缩小，相反如果二者相加小于目标值，说明左指针太小了，将其右移扩大，直到两指针相遇，剩余子数组找完了。

注：对于三个数字都要判断是否相邻有重复的情况，要去重。

思路：先排序，然后双指针，注意去重就可以了。

 public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer>> lists=new ArrayList<ArrayList<Integer>>();
        int n=num.length;
        Arrays.sort(num);
        for (int i=0;i<n-2;i++){
            if(i!=0&&num[i]==num[i-1]) continue;
            int left=i+1;
            int right=n-1;
            int target=-num[i];
            while (left<right){
                if(num[left]+num[right]==target){
                    ArrayList<Integer> list=new ArrayList<Integer>();
                    list.add(num[i]);
                    list.add(num[left]);
                    list.add(num[right]);
                    lists.add(list);
                    while (left+1<right&&num[left]==num[left+1]) left++;
                    while (right-1>left&&num[right]==num[right-1]) right--;
                    left++;
                    right--;
                }else if(num[left]+num[right]>target) right--;
                else left++;
            }

        }
        return lists;
    }