【C语言刷LeetCode】15. 三数之和(M)

【

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

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

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
示例 2：

输入：nums = [0,1,1]
输出：[]
示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
 

提示：

3 <= nums.length <= 3000
-105 <= nums[i] <= 105

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

】

一个数遍历，在后面的数中找两个数，想到滑窗，

这道题主要考性能，所以很容易超时，必须想很多去重方法，当然先给数组排个序

1. 当nums[i] > 0, 那就不用找了，直接break

2. 当nums[i]跟上一个元素nums[i -1]一样，那么需要跳过

3. 滑窗时遇到nums[j]相同时，需要跳过，j++

4. 滑窗时遇到nums[k]相同时，需要跳过，k--

5. C语言数组最大的大小 size * (size - 1),因为两个数确定了，这个三元组就确定了

6. 二维数组的第二维不用一开始就申请，可以找到了再申请

7. 因为考性能，所以二维数组就不要memset了

8. returnColumnSizes[0][i] 的赋值放到最后，按照实际个数赋值

9. 找到符合要求的三元组后，j++, k--

int Cmp(const void *a, const void *b)
{
    return *(int *)a - *(int *)b;
}
 
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
    int i, j, k;
    int **retarr;
    int icnt = 0;
    int sum = 0;
    int size = numsSize * numsSize;
 
    retarr = (int **)malloc(sizeof(int *) * size);
    returnColumnSizes[0] = malloc(sizeof(int) * size);
 
    qsort(nums, numsSize, sizeof(int), Cmp);
 
    for (i = 0; i < numsSize - 2; i++) { // 第一个数遍历，注意遍历边界到 numsSize - 2
        if (nums[i] > 0) { // 去重
            break;
        }
 
        if (i > 0 && nums[i] == nums[i - 1]) { // 去重
            continue;
        }
 
        j = i + 1;
        k = numsSize - 1;
 
        while (j < k) {
            sum = nums[i] + nums[j] + nums[k];
            
            if (sum == 0) {
                retarr[icnt] = malloc(sizeof(int) * 3);
                retarr[icnt][0] = nums[i];
                retarr[icnt][1] = nums[j];
                retarr[icnt][2] = nums[k];
                icnt++;
 
                while(j < k && nums[j] == nums[j + 1]) { // 去重
                    j++;
                }
 
                while(j < k && nums[k] == nums[k - 1]) { // 去重
                    k--;
                }
 
                j++;
                k--;
            } else if (sum < 0) {
                j++;
            } else if (sum > 0) {
                k--;
            }          
        }
    }
 
    for (i = 0; i < icnt; i++) {
        returnColumnSizes[0][i] = 3;
    }
 
    *returnSize = icnt;
    return retarr;
}