当前位置:网站首页>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;
}
六、运行结果
边栏推荐
- 巴比特 | 元宇宙每日必读:中国互联网企业涌入元宇宙的群像:“只有各种求生欲,没有前瞻创新的雄心”...
- Do you really think binary search is easy
- GET/POST/PUT/PATCH/DELETE含义
- leetcode841. Keys and rooms (medium)
- Uncaught TypeError: Cannot red propertites of undefined(reading ‘beforeEach‘)解决方案
- After the hot update of uniapp, "mismatched versions may cause application exceptions" causes and Solutions
- 软件测试界的三无简历,企业拿什么来招聘你,石沉大海的简历
- Jerry's general penetration test - do data transmission with app Communication [article]
- word中把带有某个符号的行全部选中,更改为标题
- Cookie Technology & session Technology & ServletContext object
猜你喜欢
Multi attribute object detection on rare aircraft data sets: experimental process using yolov5
杰理之BLE【篇】
1091: two or three things in childhood (multi instance test)
qt颜色与字符串、uint相互转换
Uncaught TypeError: Cannot red propertites of undefined(reading ‘beforeEach‘)解决方案
Crawling exercise: Notice of crawling Henan Agricultural University
JDBC learning notes
How Navicat imports MySQL scripts
[online problem processing] how to kill the corresponding process when the MySQL table deadlock is caused by the code
When the Jericho development board is powered on, you can open the NRF app with your mobile phone [article]
随机推荐
杰理之蓝牙设备想要发送数据给手机,需要手机先打开 notify 通道【篇】
Bloom taxonomy
Lesson 12 study notes 2022.02.11
C - Inheritance - hidden method
Uncaught typeerror: cannot red properties of undefined (reading 'beforeeach') solution
leetcode1020. Number of enclaves (medium)
Jerry's general penetration test - do data transmission with app Communication [article]
OpenJudge NOI 2.1 1661:Bomb Game
Is software testing outsourcing going or not? Three years' real outsourcing experience tells you
剪映的相关介绍
Typescript interface properties
【JDBC】快速入门教程
位运算异或
Week6 weekly report
jmeter性能测试步骤实战教程
leetcode841. Keys and rooms (medium)
[MySQL learning notes 32] mvcc
Crawling exercise: Notice of crawling Henan Agricultural University
1091: two or three things in childhood (multi instance test)
Structure summary of SystemVerilog integrable model