LeetCode：15.三数之和

题目

LeetCode: 3Sum

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

注意：答案中不可以包含重复的三元组。

示例：

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

思路

本题使用双指针法：

首先数组需有序，指针位置如图，若三个数之和大于目标值，说明和太大，需要一个更小的数，所以只能是右指针指向小一点的数，反之左指针指向大一点的数

我的代码由于用的是c语言，在排序和去重没用STL提供的模板，而是写了个冒泡和遍历查找，在效率上可能没有用set的效率高

代码

查看更多LeetCode代码

/**
 * Return an array of arrays of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
int** threeSum(int* nums, int numsSize, int* returnSize) {
    int i = 0, start = 0;
    int** ret = NULL;//由于要动态返回，也不知道多少组，没有c++方便，干脆等会再申请
    *returnSize = 0;
    int flag = 0;//falg作为去除重复数组标记用
    for (i = 1; i < numsSize; i++)
    {
        //先排序，这里选的是插入排序，为了速度可以选择快排或者归并
        int tmp = nums[i];
        for (start = i - 1; start >= 0; start--)
        {
            if (tmp < nums[start])
            {
                nums[start + 1] = nums[start];
            }
            else
            {
                break;
            }
        }
        nums[start + 1] = tmp;
    }
    i = 0;
    while (nums[i] <= 0)
    {
        //要想结果等于0，必定有一个数小于等于0
        //i固定，找另外两个数
        int start = i + 1;
        int end = numsSize - 1;
        while (start < end)
        {
            //这里我选择的是左右指针法
            if (nums[i] + nums[start] + nums[end] > 0)
            {
                //当三数之和大于0，必定需要其中一个数减少，只能是end左移
                end--;
            }
            else if (nums[i] + nums[start] + nums[end] < 0)
            {
                //结果小于0，需要start右移才有可能和增加
                start++;
            }
            else if (nums[i] + nums[start] + nums[end] == 0)
            {
                if (ret == NULL)
                {
                    //为空，直接申请不需要考虑别的，因为是第一组数据
                    ret = (int**)malloc(sizeof(int*));
                    *ret = (int*)malloc(sizeof(int) * 3);
                }
                else
                {
                    //进入此至少有一组数据，由于不能重复，所以得先去重
                    for (int x = *returnSize; x > 0; x--)
                    {
                        //从后往前找，重复的数据必定是相隔不远的
                        if (nums[i] == *(*(ret + x) + 0) && nums[start] == *(*(ret + x) + 1) && nums[end] == *(*(ret + x) + 2))
                        {
                            //有重复，
                            flag = 1;
                            break;
                        }
                    }
                    if (flag == 0)
                    {
                        //没有重复就申请空间
                        ret = (int**)realloc(ret, sizeof(int*) * ((*returnSize) + 1));
                        *(ret + (*returnSize)) = (int*)malloc(sizeof(int) * 3);
                    }
                }
                if (flag == 0)
                {
                    //没有重复就存储数据
                    *(*(ret + (*returnSize)) + 0) = nums[i];
                    *(*(ret + (*returnSize)) + 1) = nums[start];
                    *(*(ret + (*returnSize)) + 2) = nums[end];
                    (*returnSize)++;
                }
                flag = 0;//标记重新置0
                start++;//没找玩，start++找下一组
            }
        }
        i++;//i要继续往后查找
    }
    return ret;
}