难度：中等
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]

思路：将数组排序，遍历数组，取头取尾与当前元素相加，判断大小，相等则存取数据，大于则尾部指针前移，小于则首部指针后移直到找到三数相加和符合条件。

Java实现：

public class Sum3 {
public static void main(String[] args) {
    //int[] nums = {1,-1,-1,0};
    //int[] nums = {-1,0,1,2,-1,-4};
    int[] nums = {-2,0,0,2,2};
    List<List<Integer>> list = threeSum(nums);
    for (int i = 0; i < list.size(); i++) {
        List<Integer> arr = list.get(i);
        for (int j = 0; j < arr.size(); j++) {
            System.out.print(arr.get(j)+" ");
        }
        System.out.println();
    }
}
public static List<List<Integer>> threeSum(int[] nums) {
    //排序
    int left=0;
    int right=nums.length-1;
    quickSort(nums,left,right);
    List<List<Integer>> list = new ArrayList<>();
    for(int i=0;i<nums.length-2;i++) {
        if(nums[i]>0)break;
        if(i>0&&nums[i]==nums[i-1])continue;
        int start = i+1;
        int end = nums.length-1;
        while(start<end) {
            if(nums[i]+nums[start]+nums[end]==0) {
                List<Integer> v = new ArrayList<>();
                v.add(nums[i]);v.add(nums[start]);v.add(nums[end]);
                list.add(v);
                while(start<end&&nums[start]==nums[start+1])start++;
                while(start<end&&nums[end]==nums[end-1])end--;
                start++;end--;
            }else if(nums[i]+nums[start]+nums[end]>0) {
                end--;
            }else if(nums[i]+nums[start]+nums[end]<0) {
                start++;
            }
        }
    }
    return list;
}
    //排序算法
    public static void quickSort(int[] nums,int left,int right) {
        if(left>right) return;
        int key = nums[left];
        int i=left;
        int j=right;
        while(i<j) {
            while(i<j&&key<=nums[j])j--;
            nums[i] = nums[j];
            while(i<j&&key>=nums[i])i++;
            nums[j] = nums[i];
        }
        nums[i] = key;
        quickSort(nums,left,i-1);
        quickSort(nums,i+1,right);
    }
}

C语言实现：

int main(int argc, const char * argv[]) {
    @autoreleasepool {
//        int nums[6] = {-1,0,1,2,-1,-4};
        int nums[] = {-7,-4,-6,6,4,-6,-9,-10,-7,5,3,-1,-5,8,-1,-2,-8,-1,5,-3,-5,4,2,-5,-4,4,7};
        int length = sizeof(nums)/sizeof(int);
        int returnSize = 0;
        int** result = threeSum(nums,length,&returnSize);
        for(int i=0;i<returnSize;i++){
            int* array = result[i];
            for (int j=0; j<3; j++) {
                printf("%d ",array[j]);
            }
            printf("\n");
        }
    }
    printf("\n");
    return 0;
}
//快速排序
void quickSort(int nums[],int left,int right){
    if(left>right)return;
    int i = left;
    int j = right;
    int key = nums[left];
    while(i<j){
        while (i<j&&key<=nums[j]) j--;
        nums[i] = nums[j];
        while(i<j&&key>=nums[i])i++;
        nums[j] = nums[i];
    }
    nums[i] = key;
    quickSort(nums, left, i-1);
    quickSort(nums, i+1, right);
}
int** threeSum(int* nums, int numsSize, int* returnSize) {
    int left = 0;
    int right = numsSize-1;
    quickSort(nums,left,right);
//    int** list = (int **)malloc(sizeof(int *) * numsSize);     //分配指针数组
    //这里的内存分配最大值为c n 3,即排列组合知识; 只能使用一下方法分配空间
    int** list=(int**)malloc(sizeof(int*)*(numsSize*(numsSize-1)*(numsSize-2))/6);
    *returnSize = 0;
    for(int i=0;i<numsSize-2;i++){
        if(nums[i]>0)break;
        if(i>0&&nums[i]==nums[i-1])continue;
        int start = i+1;
        int end = numsSize-1;
        while (start<end) {
            if(nums[i]+nums[start]+nums[end]==0){
                (*returnSize)++;
                int index = (*returnSize)-1;
                list[index] = (int *)malloc(sizeof(int) * 3); //分配每个指针所指向的数组
                list[index][0] = nums[i];
                list[index][1] = nums[start];
                list[index][2] = nums[end];
                while(start<end&&nums[start]==nums[start+1])start++;
                while(start<end&&nums[end]==nums[end-1])end--;
                start++;
                end--;
            }else if(nums[i]+nums[start]+nums[end]>0){
                end--;
            }else {
                start++;
            }
        }
    }
    free(list);
    return list;
}