資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法學研究C++ 中將陣列分成和相等的子陣列
假設我們有一個包含 n 個整數的陣列，我們需要找到是否滿足以下條件的三元組 (i, j, k)：
0 < i, i + 1 < j, j + 1 < k < n - 1
子陣列 (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
sums[0] := nums[0]
for i := 1 to n-1 do −
sums[i] := sums[i-1] + nums[i]
for j := 3 to n do −
定義一個集合 s
for i := 1 to j - 2 do: −
sum1 := sums[i - 1]
sum2 := sums[j - 1] - sums[i]
if sum1 等於 sum2，則：
將 sum1 插入 s
for k := j + 2 to n - 2 do −
sum1 := sums[k - 1] - sums[j]
sum2 := sums[n - 1] - sums[k]
if sum1 等於 sum2 且 sum1 在 s 中，則：
返回 true
返回 false
示例
讓我們看看下面的實現，以便更好地理解：
#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
更新於：2020年11月16日
784 次瀏覽
廣告