当前位置：网站首页>leecode-C语言实现-15. 三数之和------思路待改进版
leecode-C语言实现-15. 三数之和------思路待改进版
2022-07-06 07:22:00 【阳光九叶草LXGZXJ】
一、题目
二、解题思路
（1）思路待改进
例如数组为：{
-1,0,1,0,3}
（1）构造一个-10^5到10^5的数组，将数据一一放入，这里为了书写方便就-5到5。
（2）放入时定义多个变量记录最大值和最小值下标及索引。
数值：-5 -4 -3 -2 -1 0 1 2 3 4 5
次数： 0 0 0 0 1 1 1 0 1 0 0
索引： 0 1 2 3 4 5 6 7 8 9 10
min max
temp
数组长度：11
MinIndex = 4
MaxIndex = 6
TempIndex = 4
MaxValue = 3
MinValue = -1
（3）如果最小值大于零，表示数组中如何相加都不可能为0，返回空值。
（4）如果最大值小于零，表示数组中如何相加都不可能为0，返回空值。
（5）如果最小值的两倍加上最大值还是大于0，说明这个最大值肯定不在最后的答案中。
-1 * 2 + 3 > 0
MaxIndex减一
MaxIndex = 6
（5）如果最大值的两倍加上最小值还是小于0，说明这个最小值肯定不在最后的答案中。
（6）判断逻辑：MaxValue + MinValue + TempValue = 0，记录下来TempIndex为5 。
-1 + 1 + 0 = 0
（7）再判断 TempIndex=5对应的值为1，说明数组中只有一个0，且没有和最大值和最小值重合，符合要求。
MaxIndex减一
MaxIndex = 6
最终二维数组添加数组：{
{
-1 0 1 } }
（8）再判断：
MinValue : -1 , MaxValue : 0 , TempValue : 1
发现TempValue : 1 超过MaxValue : 0，为重复元素，踢出。
（9）再判断：
MinValue : 0 , MaxValue : 1 , TempValue : -1
发现TempValue : 1 超过MinValue : 0，为重复元素，踢出。
（10）再判断：
MinValue : 0 , MaxValue : 0 , TempValue : 0
发现0只有两个值，这里却取了三次，踢出。
三、VS测试代码
（1）思路待改进版
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ELEMENTSIZE 3
#define INITARRAYSIZE 10000
#define RECORDARRAYSIZE 10
void PrintfArr(void *arr, int size, int elementsize);
void PrintfHeadVal();
void Printf2DimensionArray(int** Array, int num1, int num2);
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes);
int main()
{
int nums[] = {
-1,0,1,0,3 };
int numsSize = sizeof(nums) / sizeof(int);
int returnSize = 0;
int** returnColumnSizes = (int**)malloc(sizeof(int*));
PrintfArr(nums, numsSize, sizeof(int));
threeSum(nums, numsSize, &returnSize, returnColumnSizes);
return 0;
}
/* 例如数组为： 数值：-5 -4 -3 -2 -1 0 1 2 3 4 5 次数： 0 1 2 1 3 1 0 2 4 5 1 索引： 0 1 2 3 4 5 6 7 0 9 10 min max temp 数组长度：11 （1）构造一个-10^5到10^5的数组，将数据一一放入。 （2）放入时定义两个变量记录最大值和最小值下标。 （3）如果最小值大于零，表示数组中如何相加都不可能为0，返回空值。 （4）如果最大值小于零，表示数组中如何相加都不可能为0，返回空值。 （5）也就是有三个变量，MaxIndex，MinIndex，TempIndex。 （6）判断逻辑：max取值 + min取值 + temp取值 = 0，记录下来。 max取值 + min取值 + temp取值 ！= 0，不记录。 （7）min <= 0, max >= 0, temp取值 = 0 - min取值 - max取值，来判断temp的索引位。 （8）temp对应的索引位是否为0，如果 为0，不记录。 为1时需要判断是否和max、min重合，重合退出，不重合记录。大于等2，记录。 */
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
*returnSize = 0;
if (numsSize < ELEMENTSIZE)
{
return NULL;
}
int** ResArray = (int**)malloc(sizeof(int*) * INITARRAYSIZE);
int* RecordArray = (int*)malloc(sizeof(int) * (RECORDARRAYSIZE * 2 + 1));
*returnColumnSizes = (int*)malloc(sizeof(int) * INITARRAYSIZE);
int MaxIndex = RECORDARRAYSIZE + nums[0];
int MinIndex = RECORDARRAYSIZE + nums[0];
int TempValue = 0;
int MaxValue = MaxIndex - RECORDARRAYSIZE;
int MinValue = MinIndex - RECORDARRAYSIZE;
int TempIndex = 0;
int i = 0;
int j = 0;
int Flag = 0;
//初始化数组RecordArray
for ( i = 0; i < RECORDARRAYSIZE * 2 + 1; i++)
{
RecordArray[i] = 0;
}
//将nums数组中的值记录到数组RecordArray中
//记录最大最小值和索引
for ( i = 0; i < numsSize; i++)
{
MaxValue = MaxIndex - RECORDARRAYSIZE;
if (nums[i] > MaxValue)
{
MaxIndex = RECORDARRAYSIZE + nums[i];
}
MinValue = MinIndex - RECORDARRAYSIZE;
if(nums[i] < MinValue)
{
MinIndex = RECORDARRAYSIZE + nums[i];
}
RecordArray[RECORDARRAYSIZE + nums[i]]++;
}
MaxValue = MaxIndex - RECORDARRAYSIZE;
MinValue = MinIndex - RECORDARRAYSIZE;
PrintfHeadVal();
printf("数值：");
PrintfArr(RecordArray, RECORDARRAYSIZE * 2 + 1, sizeof(int));
printf("MaxIndex : %d , MaxValue : %d , MinIndex : %d , MinValue : %d\n", MaxIndex, MaxValue, MinIndex, MinValue);
//如果最小值大于零，表示数组中如何相加都不可能为0，返回空值。
//如果最大值小于零，表示数组中如何相加都不可能为0，返回空值。
if (MaxValue < 0)
{
return NULL;
}
if (MinValue > 0)
{
return NULL;
}
//下面这两个循环可以减少后面for循环的次数，加快程序效率。
//不加也可以，提升效率不大。
while ((MinValue * 2 + MaxValue > 0) && (RecordArray[MaxIndex] != 0))
{
MaxIndex--;
MaxValue = MaxIndex - RECORDARRAYSIZE;
}
while ((MinValue + MaxValue * 2 < 0) && (RecordArray[MinIndex] != 0))
{
MinIndex++;
MinValue = MinIndex - RECORDARRAYSIZE;
}
for (i = MinIndex; i <= RECORDARRAYSIZE; i++)
{
if (RecordArray[i] == 0)
{
continue;
}
MinValue = i - RECORDARRAYSIZE;
while ((MinValue * 2 + MaxValue > 0) && (RecordArray[MaxIndex] != 0))
{
MaxIndex--;
MaxValue = MaxIndex - RECORDARRAYSIZE;
}
for ( j = MaxIndex; j >= RECORDARRAYSIZE; j--)
{
if (RecordArray[j] == 0)
{
continue;
}
MaxValue = j - RECORDARRAYSIZE;
TempValue = 0 - MinValue - MaxValue;
TempIndex = TempValue + RECORDARRAYSIZE;
printf(" i : %2d , MinValue : %2d ,j : %2d , MaxValue : %2d , TempIndex : %2d , TempValue : %2d , RecordArray[TempIndex] : %2d\n",
i, MinValue, j, MaxValue, TempIndex, TempValue, RecordArray[TempIndex]);
if (RecordArray[TempIndex] > 0)
{
if ((RecordArray[TempIndex] == 1) && (j > TempIndex) && (i < TempIndex))
{
Flag = 1;
}
else if ((RecordArray[TempIndex] == 2) && (j > TempIndex) && (i <= TempIndex))
{
Flag = 1;
}
else if ((RecordArray[TempIndex] == 2) && (j >= TempIndex) && (i < TempIndex))
{
Flag = 1;
}
else if ((RecordArray[TempIndex] > 2) && (j >= TempIndex) && (i <= TempIndex))
{
Flag = 1;
}
if (Flag)
{
printf("*returnSize : %d\n", *returnSize);
(*returnColumnSizes)[*returnSize] = ELEMENTSIZE;//*returnColumnSizes要用括号括起来
ResArray[*returnSize] = (int*)malloc(sizeof(int) * ELEMENTSIZE);
ResArray[*returnSize][0] = MinValue;
ResArray[*returnSize][2] = MaxValue;
ResArray[*returnSize][1] = TempValue;
//printf("data : (%d , %d , %d)\n", ResArray[*returnSize][0], ResArray[*returnSize][2], ResArray[*returnSize][1]);
(*returnSize)++;
Printf2DimensionArray(ResArray, *returnSize, ELEMENTSIZE);
printf("+++++++++++++++++++++++++++++\n");
Flag = 0;
}
}
}
}
Printf2DimensionArray(ResArray, *returnSize, ELEMENTSIZE);
Printf2DimensionArray(returnColumnSizes, 1, *returnSize);
return ResArray;
}
void Printf2DimensionArray(int** Array, int num1, int num2)
{
int i, j;
printf("{");
for ( i = 0; i < num1; i++)
{
printf("{");
for ( j = 0; j < num2; j++)
{
printf("%2d ", Array[i][j]);
}
printf("} ");
}
printf("} \n");
}
void PrintfHeadVal()
{
int i;
printf("表头：");
for (i = -RECORDARRAYSIZE; i <= RECORDARRAYSIZE; i++)
{
printf("%3d ", i);
}
printf("\n");
printf("索引：");
for (i = 0; i <= RECORDARRAYSIZE * 2 ; i++)
{
printf("%3d ", i);
}
printf("\n");
}
void PrintfArr(void *arr, int size, int elementsize)
{
if (elementsize == sizeof(int))
{
int *tmparr = (int*)arr;
int i;
for (i = 0; i < size; i++)
{
printf("%3d ", tmparr[i]);
}
}
else if (elementsize == sizeof(char))
{
char *tmparr = (char*)arr;
int i;
for (i = 0; i < size; i++)
{
printf("%c ", tmparr[i]);
}
}
printf("\n========================\n");
}
四、VS运行结果
五、leecode提交代码
#define ELEMENTSIZE 3
#define INITARRAYSIZE 20000
#define RECORDARRAYSIZE 100000
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
*returnSize = 0;
if (numsSize < ELEMENTSIZE)
{
return NULL;
}
int** ResArray = (int**)malloc(sizeof(int*) * INITARRAYSIZE);
int* RecordArray = (int*)malloc(sizeof(int) * (RECORDARRAYSIZE * 2 + 1));
*returnColumnSizes = (int*)malloc(sizeof(int) * INITARRAYSIZE);
int MaxIndex = RECORDARRAYSIZE + nums[0];
int MinIndex = RECORDARRAYSIZE + nums[0];
int TempValue = 0;
int MaxValue = MaxIndex - RECORDARRAYSIZE;
int MinValue = MinIndex - RECORDARRAYSIZE;
int TempIndex = 0;
int i = 0;
int j = 0;
int Flag = 0;
for ( i = 0; i < RECORDARRAYSIZE * 2 + 1; i++)
{
RecordArray[i] = 0;
}
for ( i = 0; i < numsSize; i++)
{
MaxValue = MaxIndex - RECORDARRAYSIZE;
if (nums[i] > MaxValue)
{
MaxIndex = RECORDARRAYSIZE + nums[i];
}
MinValue = MinIndex - RECORDARRAYSIZE;
if(nums[i] < MinValue)
{
MinIndex = RECORDARRAYSIZE + nums[i];
}
RecordArray[RECORDARRAYSIZE + nums[i]]++;
}
MaxValue = MaxIndex - RECORDARRAYSIZE;
MinValue = MinIndex - RECORDARRAYSIZE;
if (MaxValue < 0)
{
return NULL;
}
if (MinValue > 0)
{
return NULL;
}
while ((MinValue * 2 + MaxValue > 0) && (RecordArray[MaxIndex] != 0))
{
MaxIndex--;
MaxValue = MaxIndex - RECORDARRAYSIZE;
}
while ((MinValue + MaxValue * 2 < 0) && (RecordArray[MinIndex] != 0))
{
MinIndex++;
MinValue = MinIndex - RECORDARRAYSIZE;
}
for (i = MinIndex; i <= RECORDARRAYSIZE; i++)
{
if (RecordArray[i] == 0)
{
continue;
}
MinValue = i - RECORDARRAYSIZE;
while ((MinValue * 2 + MaxValue > 0) && (RecordArray[MaxIndex] != 0))
{
MaxIndex--;
MaxValue = MaxIndex - RECORDARRAYSIZE;
}
for ( j = MaxIndex; j >= RECORDARRAYSIZE; j--)
{
if (RecordArray[j] == 0)
{
continue;
}
MaxValue = j - RECORDARRAYSIZE;
TempValue = 0 - MinValue - MaxValue;
TempIndex = TempValue + RECORDARRAYSIZE;
if (RecordArray[TempIndex] > 0)
{
if ((RecordArray[TempIndex] == 1) && (j > TempIndex) && (i < TempIndex))
{
Flag = 1;
}
else if ((RecordArray[TempIndex] == 2) && (j > TempIndex) && (i <= TempIndex))
{
Flag = 1;
}
else if ((RecordArray[TempIndex] == 2) && (j >= TempIndex) && (i < TempIndex))
{
Flag = 1;
}
else if ((RecordArray[TempIndex] > 2) && (j >= TempIndex) && (i <= TempIndex))
{
Flag = 1;
}
if (Flag)
{
(*returnColumnSizes)[*returnSize] = ELEMENTSIZE;
ResArray[*returnSize] = (int*)malloc(sizeof(int) * ELEMENTSIZE);
ResArray[*returnSize][0] = MinValue;
ResArray[*returnSize][2] = MaxValue;
ResArray[*returnSize][1] = TempValue;
(*returnSize)++;
Flag = 0;
}
}
}
}
return ResArray;
}
六、运行结果
边栏推荐
- Detailed explanation | detailed explanation of internal mechanism of industrial robot
- The best way to learn SEO: search engine
- LeetCode Algorithm 2181. Merge nodes between zero
- word中如何删除某符号前面或后面所有的文字
- TypeScript 函数定义
- Structure summary of SystemVerilog integrable model
- [window] when the Microsoft Store is deleted locally, how to reinstall it in three steps
- Leetcode59. spiral matrix II (medium)
- supervisor 使用文档
- The first Baidu push plug-in of dream weaving fully automatic collection Optimization SEO collection module
猜你喜欢
Wechat brain competition answer applet_ Support the flow main belt with the latest question bank file
Solution to the problem of breakthrough in OWASP juice shop shooting range
Excel的相关操作
How Navicat imports MySQL scripts
![Ble of Jerry [chapter]](/img/d8/d080ccaa4ee530ed21d62755808724.png)
Ble of Jerry [chapter]
The way to learn go (I) the basic introduction of go to the first HelloWorld
![[online problem processing] how to kill the corresponding process when the MySQL table deadlock is caused by the code](/img/93/ec9de907cae4714038bb5f95aba52b.png)
[online problem processing] how to kill the corresponding process when the MySQL table deadlock is caused by the code
word中如何删除某符号前面或后面所有的文字
学go之路（一）go的基本介绍到第一个helloworld
杰理之BLE【篇】
随机推荐
js對象獲取屬性的方法(.和[]方式)
JDBC learning notes
Project GFS data download
leetcode704. Binary search (find an element, simple, different writing)
If Jerry needs to send a large package, he needs to modify the MTU on the mobile terminal [article]
首发织梦百度推送插件全自动收录优化seo收录模块
word中把帶有某個符號的行全部選中，更改為標題
C - Inheritance - polymorphism - virtual function member (lower)
Idea console color log
jmeter性能测试步骤实战教程
Wechat official account infinite callback authorization system source code, launched in the whole network
LeetCode Algorithm 2181. Merge nodes between zero
C - Inheritance - hidden method
Typescript indexable type
【JDBC】快速入门教程
GET/POST/PUT/PATCH/DELETE含义
微信脑力比拼答题小程序_支持流量主带最新题库文件
OpenGL ES 学习初识（1）
NiO programming introduction
The author is dead? AI is conquering mankind with art