当前位置：网站首页>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;
}
六、運行結果
边栏推荐
- 软件测试界的三无简历，企业拿什么来招聘你，石沉大海的简历
- Supervisor usage document
- 作者已死？AI正用藝術征服人類
- Raspberry pie 3B update VIM
- CDN acceleration and cracking anti-theft chain function
- 杰理之开发板上电开机，就可以手机打开 NRF 的 APP【篇】
- Summary of Digital IC design written examination questions (I)
- [MySQL learning notes 30] lock (non tutorial)
- SSM learning
- Méthode d'obtention des propriétés de l'objet JS (.Et [] méthodes)
猜你喜欢
Cookie Technology & session Technology & ServletContext object
Solution to the problem of breakthrough in OWASP juice shop shooting range
L'auteur est mort? Ai utilise l'art pour conquérir l'humanité
Leetcode35. search the insertion position (simple, find the insertion position, different writing methods)
Detailed explanation | detailed explanation of internal mechanism of industrial robot
Fundamentals of C language 9: Functions
Bugku CTF daily question: do you want seeds? Blackmailed
软件测试界的三无简历，企业拿什么来招聘你，石沉大海的简历
Leetcode59. spiral matrix II (medium)
The way to learn go (I) the basic introduction of go to the first HelloWorld
随机推荐
Ble of Jerry [chapter]
Typescript void base type
Redis builds clusters
烧录场景下的源代码防泄密方案分享
智能终端设备加密防护的意义和措施
Méthode d'obtention des propriétés de l'objet JS (.Et [] méthodes)
Résumé de la structure du modèle synthétisable
Methods for JS object to obtain attributes (. And [] methods)
The way to learn go (II) basic types, variables and constants
LeetCode Algorithm 2181. Merge nodes between zero
word删除括号里内容
TypeScript void 基础类型
TypeScript 变量作用域
学go之路（一）go的基本介绍到第一个helloworld
变量的命名规则十二条
Ble of Jerry [chapter]
Structure summary of SystemVerilog integrable model
navicat如何导入MySQL脚本
Oracle column to row -- a field is converted to multiple rows according to the specified separator
Detailed explanation | detailed explanation of internal mechanism of industrial robot