当前位置:网站首页>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;
}
六、運行結果
边栏推荐
猜你喜欢
The author is dead? AI is conquering mankind with art
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
SSM learning
Cookie技术&Session技术&ServletContext对象
L'auteur est mort? Ai utilise l'art pour conquérir l'humanité
When the Jericho development board is powered on, you can open the NRF app with your mobile phone [article]
Raspberry pie serial port login and SSH login methods
Oracle column to row -- a field is converted to multiple rows according to the specified separator
MVVM of WPF
OpenGL ES 学习初识(1)
随机推荐
word删除括号里内容
位运算异或
Openjudge noi 2.1 1749: Digital Square
Emo diary 1
【mysql学习笔记30】锁(非教程)
作者已死?AI正用藝術征服人類
Establishment and operation of cloud platform open source project environment
Raspberry pie serial port login and SSH login methods
How Navicat imports MySQL scripts
L'auteur est mort? Ai utilise l'art pour conquérir l'humanité
SSM learning
Structure summary of SystemVerilog integrable model
Ble of Jerry [chapter]
Cookie Technology & session Technology & ServletContext object
navicat如何导入MySQL脚本
Markdown 中设置图片图注
Chrome view page FPS
The author is dead? AI is conquering mankind with art
变量的命名规则十二条
TS基础篇