当前位置：网站首页>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;
}
六、運行結果
边栏推荐
- Is software testing outsourcing going or not? Three years' real outsourcing experience tells you
- Jerry's ad series MIDI function description [chapter]
- qt颜色与字符串、uint相互转换
- Detailed explanation | detailed explanation of internal mechanism of industrial robot
- C - Inheritance - hidden method
- [MySQL learning notes 32] mvcc
- If Jerry needs to send a large package, he needs to modify the MTU on the mobile terminal [article]
- Uncaught typeerror: cannot red properties of undefined (reading 'beforeeach') solution
- The first Baidu push plug-in of dream weaving fully automatic collection Optimization SEO collection module
- Establishment and operation of cloud platform open source project environment
猜你喜欢
![Ble of Jerry [chapter]](/img/ce/127b597cdd238bb0c37326f5cf8265.png)
随机推荐
How MySQL merges data
Twelve rules for naming variables
LeetCode Algorithm 2181. Merge nodes between zero
Redis builds clusters
剪映的相关介绍
Jerry's ad series MIDI function description [chapter]
You deserve this high-value open-source third-party Netease cloud music player
[online problem processing] how to kill the corresponding process when the MySQL table deadlock is caused by the code
mysql如何合并数据
Raspberry pie 3B update VIM
qt颜色与字符串、uint相互转换
Typescript interface properties
Go learning --- use reflection to judge whether the value is valid
Jerry needs to modify the profile definition of GATT [chapter]
[MySQL learning notes 32] mvcc
智能终端设备加密防护的意义和措施
Introduction to the basics of network security
Cookie技术＆Session技术＆ServletContext对象
leetcode704. Binary search (find an element, simple, different writing)
word设置目录