สมมติว่าเรามีอาร์เรย์ที่มีจำนวนเต็ม n ตัว เราต้องค้นหาว่ามีแฝดสาม (i, j, k) ที่เป็นไปตามเงื่อนไขเหล่านี้หรือไม่ -
-
0
-
ผลรวมของอาร์เรย์ย่อย (0, i - 1), (i + 1, j - 1), (j + 1, k - 1) และ (k + 1, n - 1) จะเท่ากัน
อาร์เรย์ย่อย (L, R) เป็นส่วนของอาร์เรย์ดั้งเดิมโดยเริ่มจากองค์ประกอบที่จัดทำดัชนี L ไปจนถึงองค์ประกอบที่จัดทำดัชนี R
ดังนั้น หากอินพุตเป็น [1,2,1,2,1,2,1] ผลลัพธ์จะเป็น True เนื่องจาก i =1, j =3, k =5.
sum(0, i - 1) = 1 sum(0, 0) = 1 sum(i + 1, j - 1) = 1 sum(2, 2) = 1 sum(j + 1, k - 1) = 1 sum(4, 4) = 1 sum(k + 1, n - 1) = 1 sum(6, 6) = 1
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
n :=ขนาดของ nums
-
กำหนดผลรวมอาร์เรย์ของขนาด n
-
sums[0] :=nums[0]
-
สำหรับการเริ่มต้น i :=1 เมื่อฉัน
-
sums[i] :=sums[i] + (nums[i] + sums[i - 1])
-
-
สำหรับการเริ่มต้น j :=3 เมื่อ j − n อัปเดต (เพิ่ม j ขึ้น 1) ทำ −
-
กำหนดหนึ่งชุด s
-
สำหรับการเริ่มต้น i :=1 เมื่อฉัน
-
sum1 :=sums[i - 1]
-
sum2 :=sums[j - 1] - sums[i]
-
ถ้า sum1 เหมือนกับ sum2 แล้ว −
-
ใส่ sum1 ลงใน s
-
-
-
สำหรับการเริ่มต้น k :=j + 2 เมื่อ k
-
sum1 :=sums[k - 1] - sums[j]
-
sum2 :=sums[n - 1] - sums[k]
-
ถ้า sum1 เหมือนกับ sum2 และ sum1 อยู่ใน s แล้ว −
-
คืนความจริง
-
-
-
-
คืนค่าเท็จ
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool splitArray(vector<int>& nums) {
int n = nums.size();
vector<int> sums(n);
sums[0] = nums[0];
for (int i = 1; i < n; i++) {
sums[i] += (nums[i] + sums[i - 1]);
}
for (int j = 3; j < n; j++) {
set<int> s;
for (int i = 1; i < j - 1; i++) {
int sum1 = sums[i - 1];
int sum2 = sums[j - 1] - sums[i];
if (sum1 == sum2)
s.insert(sum1);
}
for (int k = j + 2; k < n - 1; k++) {
int sum1 = sums[k - 1] - sums[j];
int sum2 = sums[n - 1] - sums[k];
if (sum1 == sum2 && s.count(sum1))
return true;
}
}
return false;
}
};
main(){
Solution ob;
vector<int> v = {1,2,1,2,1,2,1};
cout << (ob.splitArray(v));
} อินพุต
{1,2,1,2,1,2,1} ผลลัพธ์
1
