概述
算法学习复盘
算法小白最近复习完c语言和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().
*/
//排序规则
int cmp(const void *a, const void *b)
{
return *(int *)a - *(int *)b;
}
int **threeSum(int *nums, int numsSize, int *returnSize, int **returnColumnSizes)
{
*returnSize = 0;
if (numsSize < 3)
{
return NULL;
}
//利用c库函数的快排
qsort(nums, numsSize, sizeof(int), cmp);
int **ret = (int **)calloc(numsSize, sizeof(int *));
*returnColumnSizes = (int *)calloc(numsSize, sizeof(int));
int i = 0;
while ((i < numsSize) && (nums[i] < 0))
{
int j = i + 1, k = numsSize - 1;
while (j < k)
{
if ((nums[i] + nums[j] + nums[k] > 0))
{
k--;
//printf("%d,%d,%dn", nums[i], nums[j], nums[k]);
}
else if (nums[i] + nums[j] + nums[k] < 0)
{
j++;
//printf("%d,%d,%dn", nums[i], nums[j], nums[k]);
}
else
{
ret[*returnSize] = (int *)calloc(3, sizeof(int));
ret[*returnSize][0] = nums[i];
ret[*returnSize][1] = nums[j];
ret[*returnSize][2] = nums[k];
(*returnColumnSizes)[*returnSize] = 3;
(*returnSize)++;
while (nums[j] == nums[++j])
;
while (nums[k] == nums[++k])
;
//记录值
//printf("%d,%d,%dn", nums[i], nums[j], nums[k]);
}
}
i++;
}
return ret;
}
存在的问题：
1.未在意英文注释说明的内容，连题目要求做什么都没弄清楚
2.第一个while循环中有两个问题：
首先是i应当小于numsSize-2，否则在后面j和k的数组访问会越界。
然后是nums[i]应当小于等于0，否则会忽略了[0,0,0,0]的情况
3.while (nums[k] == nums[++k])
由于外层的while循环判断需要内部代码块执行完才结束，所以会出现不断循环导致越界
4.申请的内存空间不足，容易溢出
5.i自增的前提条件不对
第二版
第二版，部分通过，有些问题超时了
/**
* 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(const void *a, const void *b)
{
return *(int *)a - *(int *)b;
}
int **threeSum(int *nums, int numsSize, int *returnSize, int **returnColumnSizes)
{
*returnSize = 0;
if (numsSize < 3)
{
return NULL;
}
//利用c库函数的快排
qsort(nums, numsSize, sizeof(int), cmp);
int **ret = (int **)malloc(numsSize * numsSize * sizeof(int *));
*returnColumnSizes = (int *)malloc(numsSize * numsSize * sizeof(int));
int i = 0;
while ((i < numsSize) && (nums[i] < 0))
{
while (i > 0 && nums[i] == nums[i - 1])
{
i++;
}
int j = i + 1, k = numsSize - 1;
while (j < k)
{
if ((nums[i] + nums[j] + nums[k] > 0))
{
k--;
}
else if (nums[i] + nums[j] + nums[k] < 0)
{
j++;
}
else
{
ret[*returnSize] = (int *)malloc(3 * sizeof(int));
ret[*returnSize][0] = nums[i];
ret[*returnSize][1] = nums[j];
ret[*returnSize][2] = nums[k];
(*returnColumnSizes)[*returnSize] = 3;
(*returnSize)++;
while (nums[j] == nums[++j])
;
while (nums[k] == nums[--k])
;
}
}
i++;
}
return ret;
}
存在问题：
1.第一个while循环中有两个问题：
首先是i应当小于numsSize-2，否则在后面j和k的数组访问会越界。
2…while (nums[k] == nums[++k])
由于外层的while循环判断需要内部代码块执行完才结束，所以会出现不断循环导致越界
然后是nums[i]应当小于等于0，否则会忽略了[0,0,0,0]的情况
3.申请的内存空间不足，容易溢出
貌似除了昨天晚上用了一晚时间学会了审题hhhh
第三版
目前的最新版本
通过一个晚上学习leetcode上大神的解法，终于把自己的思路捋清楚了，才拿到ac
/**
* 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(const void *a, const void *b)
{
return *(int *)a - *(int *)b;
}
int **threeSum(int *nums, int numsSize, int *returnSize, int **returnColumnSizes)
{
//对数组排序
qsort(nums, numsSize, sizeof(int), cmp);
int i = 0, j = 0, k = 0, sum = 0;
*returnSize = 0;
//最大空间的确定
//极限情况下，第i轮有(numsSize-i)/2个(i>0)
//共有numsSize-2轮
//所以求和得
//(numsSize-1)/2+(numsSize-2)/2....+(numsSize-numsSize+2)/2
//1/4*(2+numsSize-1)*(numsSize-2)
//1/4*(numsSize+1)*(numsSize-2)
//确定上界，比它大都行
//由于不需要太精确，所以可以把1/4乘进括号内得
//(numsSize+1/4)*(numsSize-1/2)
//由于c语言的下取整，可直接取numsSize*numsSize
//我试过测试集内不存在这么极限的情况，即便是(numsSize-2)*(numsSize-2)也能ac
int **ret = (int **)calloc(numsSize * numsSize, sizeof(int *)); //为返回数组申请空间
*returnColumnSizes = (int **)calloc(numsSize * numsSize, sizeof(int *)); //为返回数组大小申请空间
while ((i < numsSize - 2) && (nums[i] <= 0))
{
if (numsSize < 3)
{ //数组不足3个元素
return NULL;
}
j = i + 1, k = numsSize - 1;
while (j < k)
{
sum = nums[i] + nums[j] + nums[k];
if (sum == 0)
{
//printf("记录：%d %d %dn", nums[i], nums[j], nums[k]);
ret[*returnSize] = (int *)calloc(3, sizeof(int));
ret[*returnSize][0] = nums[i];
ret[*returnSize][1] = nums[j];
ret[*returnSize][2] = nums[k];
(*returnColumnSizes)[*returnSize] = 3;
(*returnSize)++;
//去重
while ((j < k) && (nums[j] == nums[++j]))
;
while ((j < k) && (nums[k] == nums[--k]))
;
//去除重复的ii
//i应该小于numsSize-2,防止后面越界
}
else if (sum < 0)
{
j++;
}
else
{
k--;
}
}
while ((i < numsSize - 2) && nums[i] == nums[++i])
;
//printf("%d %d %dn", nums[i], nums[j], nums[k]);
//保证循环
}
return ret;
}
目前发现的问题：
1.申请的空间过大，存在浪费
最后
以上就是愉快小蜜蜂为你收集整理的leetcode算法题15---求三数之和算法学习复盘的全部内容，希望文章能够帮你解决leetcode算法题15---求三数之和算法学习复盘所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
![[学习报告]《LeetCode零基础指南》(第七讲) 二维数组一，二维数组简介二，做题记录三，今日收获](/uploads/reation/bcimg7.png)
发表评论 取消回复