文章目录
☀️ 前言 ☀️
算法作为极其重要的一点，是大学生毕业找工作的核心竞争力，所以为了不落后与人，开始刷力扣算法题！
🙀 作者简介 🙀
大家好，我是布小禅，一个尽力让无情的代码变得生动有趣的IT小白，很高兴能偶认识你，关注我，每天坚持学点东西，我们以后就是大佬啦！
📢 ：❤布小禅❤
📢 作者专栏：
这是我刷第 87/100 道力扣简单题
💗 一、题目描述 💗
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
示例1：
输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]]
示例2：
输入：nums = [] 输出：[]
提示：
0 <= nums.length <= 3000
-105 <= nums[i] <= 105
💁 二、题目解析 💁
思路1
\- 空数组/元素数目小于3返回空 \- 排序原数组 \- 遍历排序后的数组 \- 使用二分法找到三数之和 细节处理： \- 当前数组大于0，表示后续没有三数之和为0，结束遍历 \- 当前元素与上一次相等，跳过此次计算，去重
🏃 三、代码 🏃
☁️ C语言☁️
/** * 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(). */ /* - 空数组/元素数目小于3返回空 - 排序原数组 - 遍历排序后的数组 - 使用二分法找到三数之和 细节处理： - 当前数组大于0，表示后续没有三数之和为0，结束遍历 - 当前元素与上一次相等，跳过此次计算，去重 */ /* qsort的比较函数 */ int cmp(const void* a, const void* b) { return *(int*)a - *(int*)b; } int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){ /* 先记录返回的行数为0 */ *returnSize = 0; /* 输入为空、或元素个数小于3则返回NULL */ if (nums == NULL || numsSize < 3) { return NULL; } /* 将nums排序为升序排列 */ qsort(nums, numsSize, sizeof(int), cmp); /* 分配返回数组、返回数组的列数 */ int** ret = (int**)malloc(numsSize * numsSize * sizeof(int*)); *returnColumnSizes = (int*)malloc(numsSize * numsSize *sizeof(int)); /* 排序后的数组从头到尾进行遍历 */ for (int i = 0; i < numsSize; i++) { /* 当前数组大于0，表示后续没有三数之和为0，结束遍历 */ if (nums[i] > 0) { break; } /* 当前元素与上一次相等，跳过此次计算，去重 */ if (i > 0 && nums[i] == nums[i - 1]) { continue; } /* 定义左右指针 */ int left = i + 1, right = numsSize - 1; /* 开始查找三数之和为0 */ while (left < right) { int sum = nums[i] + nums[left] + nums[right]; if (sum == 0) { ret[*returnSize] = (int*)malloc(sizeof(int) * 3); ret[*returnSize][0] = nums[i]; ret[*returnSize][1] = nums[left]; ret[*returnSize][2] = nums[right]; /* 返回数组当前行的列数为3 */ (*returnColumnSizes)[*returnSize] = 3; /* 返回数组的行数自加1 */ (*returnSize)++; /* 对左右指针进行去重 */ while (left < right && nums[left] == nums[++left]); while (left < right && nums[right] == nums[--right]); } else if (sum < 0) { left++; } else { right--; } } } return ret; }
🌔 结语 🌔
坚持最重要，每日一题必不可少！😸
期待你的关注和督促！😛
