当前位置：网站首页>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;
}
六、運行結果
边栏推荐
- word删除括号里内容
- Wechat brain competition answer applet_ Support the flow main belt with the latest question bank file
- TS基础篇
- You deserve this high-value open-source third-party Netease cloud music player
- word中把带有某个符号的行全部选中，更改为标题
- jmeter性能测试步骤实战教程
- Go learning --- use reflection to judge whether the value is valid
- TypeScript 函数定义
- Word setting directory
- Summary of Digital IC design written examination questions (I)
猜你喜欢
![Ble of Jerry [chapter]](/img/ce/127b597cdd238bb0c37326f5cf8265.png)
Ble of Jerry [chapter]
navicat如何导入MySQL脚本
leetcode1020. Number of enclaves (medium)
Redis builds clusters
Relevant introduction of clip image
【MySQL学习笔记32】mvcc
Lesson 12 study notes 2022.02.11
Establishment and operation of cloud platform open source project environment
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
![[window] when the Microsoft Store is deleted locally, how to reinstall it in three steps](/img/57/ee979a7db983ad56f0df7345dbc91f.jpg)
[window] when the Microsoft Store is deleted locally, how to reinstall it in three steps
随机推荐
TypeScript 变量作用域
js對象獲取屬性的方法(.和[]方式)
Thought map of data warehouse construction
NiO programming introduction
L'auteur est mort? Ai utilise l'art pour conquérir l'humanité
mysql如何合并数据
杰理之BLE【篇】
Structure summary of SystemVerilog integrable model
Word delete the contents in brackets
[online problem processing] how to kill the corresponding process when the MySQL table deadlock is caused by the code
TS基础篇
Detailed explanation | detailed explanation of internal mechanism of industrial robot
[MySQL learning notes 30] lock (non tutorial)
Cookie技术＆Session技术＆ServletContext对象
网络安全基础介绍
Methods for JS object to obtain attributes (. And [] methods)
Oracle column to row -- a field is converted to multiple rows according to the specified separator
The best way to learn SEO: search engine
【JDBC】快速入门教程
Chrome view page FPS