当前位置：网站首页>leecode-C語言實現-15. 三數之和------思路待改進版
leecode-C語言實現-15. 三數之和------思路待改進版
2022-07-06 07:24: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;
}
六、運行結果
边栏推荐
- Typescript variable scope
- Summary of Digital IC design written examination questions (I)
- qt颜色与字符串、uint相互转换
- 烧录场景下的源代码防泄密方案分享
- After the hot update of uniapp, "mismatched versions may cause application exceptions" causes and Solutions
- Set picture annotation in markdown
- 杰理之AD 系列 MIDI 功能说明【篇】
- 网络安全基础介绍
- Babbitt | metauniverse daily must read: the group image of Chinese Internet enterprises pouring into metauniverse: "there are only various survival desires, and there is no ambition for forward-lookin
- Structure summary of SystemVerilog integrable model
猜你喜欢
How are the open source Netease cloud music API projects implemented?
Cookie Technology & session Technology & ServletContext object
Idea console color log
Wechat brain competition answer applet_ Support the flow main belt with the latest question bank file
【MySQL学习笔记32】mvcc
杰理之开发板上电开机，就可以手机打开 NRF 的 APP【篇】
You deserve this high-value open-source third-party Netease cloud music player
Upgraded wechat tool applet source code for mobile phone detection - supports a variety of main traffic modes
JDBC学习笔记
Seriously recommend several machine learning official account
随机推荐
烧录场景下的源代码防泄密方案分享
2022年Instagram运营小技巧简单讲解
Configure raspberry pie access network
supervisor 使用文档
OpenJudge NOI 2.1 1749:数字方格
Simple and understandable high-precision addition in C language
Twelve rules for naming variables
多线程和并发编程（二）
First knowledge of OpenGL es learning (1)
Win10 64 bit Mitsubishi PLC software appears oleaut32 DLL access denied
You deserve this high-value open-source third-party Netease cloud music player
智能终端设备加密防护的意义和措施
Memory error during variable parameter overload
TypeScript 变量作用域
Path analysis model
Related operations of Excel
杰理之BLE【篇】
OpenGL ES 学习初识（1）
Markdown 中设置图片图注
word设置目录