当前位置:网站首页>1013. Divide the array into three parts equal to and
1013. Divide the array into three parts equal to and
2022-07-06 16:07:00 【mrbone9】
Address :
Power button https://leetcode-cn.com/problems/partition-array-into-three-parts-with-equal-sum/
subject :
Give you an array of integers arr, Only can it be divided into three and equal Non empty Return only when partial true, Otherwise return to false.
Formally , If you can find the index i + 1 < j And meet (arr[0] + arr[1] + ... + arr[i] == arr[i + 1] + arr[i + 2] + ... + arr[j - 1] == arr[j] + arr[j + 1] + ... + arr[arr.length - 1]) You can divide the array into three equal parts .
Example 1:
Input :arr = [0,2,1,-6,6,-7,9,1,2,0,1] Output :true explain :0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1 |
Example 2:
Input :arr = [0,2,1,-6,6,7,9,-1,2,0,1] Output :false |
Example 3:
Input :arr = [3,3,6,5,-2,2,5,1,-9,4] Output :true explain :3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4 |
Tips :
3 <= arr.length <= 5 * 104 -104 <= arr[i] <= 104 |
source : Power button (LeetCode)
link :https://leetcode-cn.com/problems/partition-array-into-three-parts-with-equal-sum
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
Ideas :
Since it is divided into three groups and , Then first of all, ask and , Every part and is its 1/3
If the sum cannot be 3 to be divisible by , direct false
Use double pointers to separate from the array [0], Array [len-1] Close to the middle , Find the left value and , Right value sum
Intermediate and = The sum of the - L value and - Right value sum
The pit here is :
1. Can't find L value and = Right value sum , Just jump out of the loop , At this time, the left value has not reached 1/3, Nature needs to continue to accumulate
2. Can't find L value and = Right value sum , And equal to 1/3 , Jump out of the loop and find the middle sum is also equal , There is a possibility that
The sum of the = 0, L value and = Right value sum = 0, such as [1,-1, -1, 1]
So it also depends on whether the number of the middle number is 0, Only when it is not, can we continue to judge
There are many calculations in this way , And consider more boundaries , The test case has a high probability of error
Another idea is relatively simple , Reference method 2
Method 1 、 Double pointer summation
bool canThreePartsEqualSum(int* arr, int arrSize){
int goal = 0;
int lsum = 0, msum = 0, rsum = 0;
int sums = 0;
int cnt = arrSize;
int i,j;
for(i=0; i<arrSize; i++)
sums += arr[i];
if(sums % 3 != 0)
return false;
goal = sums/3;
i = 0;
j = arrSize - 1;
lsum += arr[i];
rsum += arr[arrSize-1];
cnt-=2;
while( cnt > 0)
{
if(lsum != goal)
{
i++;
lsum += arr[i];
cnt--;
}
if(rsum != goal)
{
j--;
rsum += arr[j];
cnt--;
}
if(lsum == goal && lsum == rsum)
break;
}
msum = sums - lsum - rsum;
if(cnt > 0 && lsum == msum && rsum == msum)
return true;
else
return false;
}
Method 2 、 Find the number of multiples
We know 1/3 And , Then at least there is 3 Such a sum , There may also be more , For example, He Wei 0 perhaps 3n A combination like this
So we only need two steps to complete
1. Statistical sum
2. Ask again 1/3 And , Number of Statistics ++, If the number of statistics is less than 3 , That's it false
bool canThreePartsEqualSum(int* arr, int arrSize){
int sum = 0;
int tmp = 0;
int goal = 0;
int cnt = 0;
int i;
for(i=0; i<arrSize; i++)
sum += arr[i];
if(sum % 3 != 0)
return false;
goal = sum / 3;
for(i=0; i<arrSize; i++)
{
tmp += arr[i];
if(tmp == goal)
{
cnt++;
tmp = 0;
}
}
if(cnt < 3)
return false;
return true;
}
边栏推荐
- STM32 learning record: LED light flashes (register version)
- 【练习-3】(Uva 442)Matrix Chain Multiplication(矩阵链乘)
- Find 3-friendly Integers
- [exercise-7] (UVA 10976) fractions again?! (fraction split)
- F - birthday cake (Shandong race)
- C basic grammar
- Determine the Photo Position
- Truck History
- Opencv learning log 16 paperclip count
- Interesting drink
猜你喜欢
D - Function(HDU - 6546)女生赛
Penetration test 2 --- XSS, CSRF, file upload, file inclusion, deserialization vulnerability
Information security - threat detection - detailed design of NAT log access threat detection platform
【高老师UML软件建模基础】20级云班课习题答案合集
【练习-5】(Uva 839)Not so Mobile(天平)
Matlab comprehensive exercise: application in signal and system
Determine the Photo Position
1010 things that college students majoring in it must do before graduation
Penetration test (3) -- Metasploit framework (MSF)
快速转 TypeScript 指南
随机推荐
MySQL import database error [err] 1273 - unknown collation: 'utf8mb4_ 0900_ ai_ ci’
7-1 懂的都懂 (20 分)
Interesting drink
HDU - 6024 Building Shops(女生赛)
HDU - 6024 building shops (girls' competition)
JS调用摄像头
【高老师软件需求分析】20级云班课习题答案合集
区间和------离散化
Hdu-6025-prime sequence (girls' competition)
The concept of C language array
MySQL授予用户指定内容的操作权限
渗透测试 ( 5 ) --- 扫描之王 nmap、渗透测试工具实战技巧合集
If you want to apply for a programmer, your resume should be written like this [essence summary]
【练习-3】(Uva 442)Matrix Chain Multiplication(矩阵链乘)
基于web的照片数码冲印网站
Differential (one-dimensional, two-dimensional, three-dimensional) Blue Bridge Cup three body attack
渗透测试 2 --- XSS、CSRF、文件上传、文件包含、反序列化漏洞
Penetration test (8) -- official document of burp Suite Pro
Find 3-friendly Integers
PySide6 信号、槽