当前位置：网站首页>Leecode-c language implementation -15 Sum of three ----- ideas to be improved
Leecode-c language implementation -15 Sum of three ----- ideas to be improved
2022-07-06 07:25:00 【Sunshine clover lxgzxj】
One 、 subject
Two 、 Their thinking
（1） Ideas need to be improved
For example, the array is ：{
-1,0,1,0,3}
（1） Construct a -10^5 To 10^5 Array of , Put the data one by one , Here for the convenience of writing -5 To 5.
（2） Define multiple variables to record the maximum and minimum subscripts and indexes when placing .
The number ：-5 -4 -3 -2 -1 0 1 2 3 4 5
frequency ： 0 0 0 0 1 1 1 0 1 0 0
Indexes ： 0 1 2 3 4 5 6 7 8 9 10
min max
temp
The length of the array ：11
MinIndex = 4
MaxIndex = 6
TempIndex = 4
MaxValue = 3
MinValue = -1
（3） If the minimum value is greater than zero , It means that no addition in the array can be 0, Returns a null value .
（4） If the maximum value is less than zero , It means that no addition in the array can be 0, Returns a null value .
（5） If twice the minimum plus the maximum is still greater than 0, It shows that this maximum value is definitely not in the final answer .
-1 * 2 + 3 > 0
MaxIndex Minus one
MaxIndex = 6
（5） If twice the maximum plus the minimum is still less than 0, It shows that this minimum value is definitely not in the final answer .
（6） Judgment logic ：MaxValue + MinValue + TempValue = 0, recorded TempIndex by 5 .
-1 + 1 + 0 = 0
（7） To determine TempIndex=5 The corresponding value is 1, Explain that there is only one in the array 0, And it does not coincide with the maximum and minimum values , Meet the requirements .
MaxIndex Minus one
MaxIndex = 6
Finally, add an array to the two-dimensional array ：{
{
-1 0 1 } }
（8） To determine ：
MinValue : -1 , MaxValue : 0 , TempValue : 1
Find out TempValue : 1 exceed MaxValue : 0, For repeating elements , Kicked out .
（9） To determine ：
MinValue : 0 , MaxValue : 1 , TempValue : -1
Find out TempValue : 1 exceed MinValue : 0, For repeating elements , Kicked out .
（10） To determine ：
MinValue : 0 , MaxValue : 0 , TempValue : 0
Find out 0 There are only two values , Here I took it three times , Kicked out .
3、 ... and 、VS Test code
（1） Ideas need to be improved
#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;
}
/* For example, the array is ： The number ：-5 -4 -3 -2 -1 0 1 2 3 4 5 frequency ： 0 1 2 1 3 1 0 2 4 5 1 Indexes ： 0 1 2 3 4 5 6 7 0 9 10 min max temp The length of the array ：11 （1） Construct a -10^5 To 10^5 Array of , Put the data one by one . （2） Define two variables to record the maximum and minimum subscripts when inserting . （3） If the minimum value is greater than zero , It means that no addition in the array can be 0, Returns a null value . （4） If the maximum value is less than zero , It means that no addition in the array can be 0, Returns a null value . （5） That is, there are three variables ,MaxIndex,MinIndex,TempIndex. （6） Judgment logic ：max Value + min Value + temp Value = 0, recorded . max Value + min Value + temp Value ！= 0, Don't record . （7）min <= 0, max >= 0, temp Value = 0 - min Value - max Value , To judge temp The index of the bit . （8）temp Whether the corresponding index bit is 0, If by 0, Don't record . by 1 You need to judge whether it is with max、min coincidence , Coincident exit , Non coincident records . Greater than, etc 2, Record . */
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;
// Initialize array RecordArray
for ( i = 0; i < RECORDARRAYSIZE * 2 + 1; i++)
{
RecordArray[i] = 0;
}
// take nums The values in the array are recorded in the array RecordArray in
// Record the maximum and minimum values and index
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(" The number ：");
PrintfArr(RecordArray, RECORDARRAYSIZE * 2 + 1, sizeof(int));
printf("MaxIndex : %d , MaxValue : %d , MinIndex : %d , MinValue : %d\n", MaxIndex, MaxValue, MinIndex, MinValue);
// If the minimum value is greater than zero , It means that no addition in the array can be 0, Returns a null value .
// If the maximum value is less than zero , It means that no addition in the array can be 0, Returns a null value .
if (MaxValue < 0)
{
return NULL;
}
if (MinValue > 0)
{
return NULL;
}
// The following two cycles can reduce the following for Number of cycles , Speed up program efficiency .
// It's OK to , The efficiency is not improved .
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 Put it in parentheses
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(" Header ：");
for (i = -RECORDARRAYSIZE; i <= RECORDARRAYSIZE; i++)
{
printf("%3d ", i);
}
printf("\n");
printf(" Indexes ：");
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");
}
Four 、VS Running results
5、 ... and 、leecode Submission code
#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;
}
6、 ... and 、 Running results
边栏推荐
- LeetCode Algorithm 2181. Merge nodes between zero
- 杰理之BLE【篇】
- How Navicat imports MySQL scripts
- Bugku CTF daily question: do you want seeds? Blackmailed
- Week6 weekly report
- Bit operation XOR
- Uncaught typeerror: cannot red properties of undefined (reading 'beforeeach') solution
- Methods for JS object to obtain attributes (. And [] methods)
- First knowledge of OpenGL es learning (1)
- You deserve this high-value open-source third-party Netease cloud music player
猜你喜欢
JDBC learning notes
How are the open source Netease cloud music API projects implemented?
![When the Jericho development board is powered on, you can open the NRF app with your mobile phone [article]](/img/3e/3d5bff87995b4a9fac093a6d9f9473.png)
When the Jericho development board is powered on, you can open the NRF app with your mobile phone [article]
Excel的相关操作
How Navicat imports MySQL scripts
leetcode1020. Number of enclaves (medium)
ORACLE列转行--某字段按指定分隔符转多行
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
word中如何删除某符号前面或后面所有的文字
Detailed explanation | detailed explanation of internal mechanism of industrial robot
随机推荐
杰理之蓝牙设备想要发送数据给手机，需要手机先打开 notify 通道【篇】
How to configure GUI guide development environment
Ble of Jerry [chapter]
TS基础篇
Leetcode 78: subset
TypeScript 变量作用域
Word delete the contents in brackets
Typescript interface and the use of generics
烧录场景下的源代码防泄密方案分享
Raspberry pie serial port login and SSH login methods
The way to learn go (II) basic types, variables and constants
Select all the lines with a symbol in word and change them to titles
Thought map of data warehouse construction
Typescript function definition
[MySQL learning notes 30] lock (non tutorial)
Idea console color log
mysql如何合并数据
leetcode704. Binary search (find an element, simple, different writing)
After the hot update of uniapp, "mismatched versions may cause application exceptions" causes and Solutions
软件测试界的三无简历，企业拿什么来招聘你，石沉大海的简历