[Leetcode15]三数之和

重刷一遍相向双指针 题目 leetcode15

https://leetcode.cn/problems/3sum/

类似的题目还有leetcode16

leetcode16
解答思路

关键点

快排 + 双指针

1： 快速排序，之后使用双指针遍历对应的位置，求解
2： 主要是在确定了第一个值，后通过双指针的方式，确定出来其余两个值
3： 将结果统计出来
4： 返回的结果数量是可以看做是对于numsSize的组合
C^2_{numsSize}CnumsSize2
但是为什么不是C^3_{numsSize}CnumsSize3呢
因为在确定前两个数值后，最后一个数值是固定的。所以是C^2_{numsSize}CnumsSize2
​

• C语言代码范例
  其实可以在nums[i] + nums[left] + nums[right] ！= 0的情况下也添加快速过滤。提高代码运行效率。
  C语言主要掌握的是二维malloc数组的申请，和二级指针的内存申请。

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */

int cmp(void *a, void *b)
{
    return *(int *)a - *(int *)b;
}

int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
    qsort(nums, numsSize, sizeof(int), cmp);
    int **res = (int **)malloc(sizeof(int *) * numsSize * numsSize);

    int i;
    int left;
    int right;
    int resSizeTmp = 0;

    int left_record;
    int right_record;
    for (i = 0; i < numsSize - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }
        left = i + 1;
        right = numsSize - 1;

        if (nums[i] + nums[left] + nums[left + 1] > 0) {
            break;
        }

        while (left < right) {
            if (nums[i] + nums[left] + nums[right] > 0) {
                right--;
            } else if (nums[i] + nums[left] + nums[right] < 0) {
                left++;
            } else {

                res[resSizeTmp] = (int *)malloc(sizeof(int) * 3);
                res[resSizeTmp][0] = nums[i];
                res[resSizeTmp][1] = nums[left];
                res[resSizeTmp][2] = nums[right];
                resSizeTmp++;
                // 存储数据后迅速过滤所有重复数据
                while(left < right && nums[left] == nums[++left]);
                while(left < right && nums[right] == nums[--right]);

            }
            left_record = nums[left];
            right_record = nums[right];
        }
    }

    *returnSize = resSizeTmp;
    *returnColumnSizes = (int *)malloc(sizeof(int) * resSizeTmp);
    for (int i = 0; i < resSizeTmp; i++) {
        (*returnColumnSizes)[i] = 3;
    }

    return res;
}

• C++ 做法，思路与C语言相似，学习一下vector的用法
  用sort函数进行排序。

#include 
using namespace std;
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {


        int n = nums.size();
        sort(nums.begin(), nums.end());
        int i;
        int left;
        int right;
        vector<vector<int>> res;

        for (i = 0; i < n - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1])
            {    
                continue;
            }

            left = i + 1;
            right = n - 1;

            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    vector<int> tmp;
                    tmp.push_back(nums[i]);
                    tmp.push_back(nums[left]);
                    tmp.push_back(nums[right]);
                    res.push_back(tmp);

                    while(left < right && nums[left] == nums[++left]);
                    while(left < right && nums[right] == nums[--right]);
                } else if (sum < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        
        return res;
    }
};