資訊專欄INFORMATION COLUMN
Problem
Given an array with n integers, you need to find if there are triplets (i, j, k) which satisfies following conditions:
0 < i, i + 1 < j, j + 1 < k < n - 1
Sum of subarrays (0, i - 1), (i + 1, j - 1), (j + 1, k - 1) and (k + 1, n - 1) should be equal.
where we define that subarray (L, R) represents a slice of the original array starting from the element indexed L to the element indexed R.
Example:
Input: [1,2,1,2,1,2,1]
Output: True
Explanation:
i = 1, j = 3, k = 5.
sum(0, i - 1) = sum(0, 0) = 1
sum(i + 1, j - 1) = sum(2, 2) = 1
sum(j + 1, k - 1) = sum(4, 4) = 1
sum(k + 1, n - 1) = sum(6, 6) = 1
Note:
1 <= n <= 2000.
Elements in the given array will be in range [-1,000,000, 1,000,000].
class Solution {
public boolean splitArray(int[] nums) {
if (nums == null || nums.length < 7) return false;
int len = nums.length;
int[] sum = new int[len];
sum[0] = nums[0];
for (int i = 1; i < len; i++) {
sum[i] = sum[i-1]+nums[i];
}
// 0 ~ i-1 | i+1 ~ mid-1 | mid+1 ~ k-1 | k+1 ~ len-1
for (int mid = 3; mid < len-3; mid++) {
Set set = new HashSet<>();
for (int i = 1; i <= mid-2; i++) {
//save quarter sum into hashset
if (sum[i-1] == sum[mid-1]-sum[i]) set.add(sum[i-1]);
}
for (int k = mid+2; k <= len-2; k++) {
if (sum[len-1]-sum[k] == sum[k-1]-sum[mid]) {
int quarterSum = sum[len-1]-sum[k];
if (set.contains(quarterSum)) return true;
}
}
}
return false;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/72407.html
摘要：對進行序列化和反序列化避免使用和構(gòu)造函數(shù)使用和構(gòu)造函數(shù)是非常昂貴的操作，因為每次他們都會調(diào)用腳本引擎將源代碼轉(zhuǎn)換成可執(zhí)行代碼。 原文：45 Useful JavaScript Tips, Tricks and Best Practices 譯文：45個有用的JavaScript技巧，竅門和最佳實踐 譯者：dwqs 在這篇文章中，我將分享一些JavaScript常用的技巧，竅門和最...
摘要：使用閉包實現(xiàn)私有變量譯者添加未在構(gòu)造函數(shù)中初始化的屬性在語句結(jié)尾處使用分號在語句結(jié)尾處使用分號是一個很好的實踐?？偨Y(jié)我知道還有很多其他的技巧，竅門和最佳實踐，所以如果你有其他想要添加或者對我分享的這些有反饋或者糾正，請在評論中指出。 showImg(http://segmentfault.com/img/bVbJnR); 如你所知，JavaScript是世界上第一的編程語言(編者注：2...
摘要：數(shù)組元素刪除應(yīng)使用。用來序列化與反序列化結(jié)果為的值與對象相同不要使用或者函數(shù)構(gòu)造器和函數(shù)構(gòu)造器的開銷較大，每次調(diào)用，引擎都要將源代碼轉(zhuǎn)換為可執(zhí)行的代碼。 收藏自 JavaScript奇技淫巧45招 JavaScript是一個絕冠全球的編程語言，可用于Web開發(fā)、移動應(yīng)用開發(fā)（PhoneGap、Appcelerator）、服務(wù)器端開發(fā)（Node.js和Wakanda）等等。JavaSc...
Problem Given a binary tree with n nodes, your task is to check if its possible to partition the tree to two trees which have the equal sum of values after removing exactly one edge on the original tr...
Problem Given an array of integers nums and a positive integer k, find whether its possible to divide this array into k non-empty subsets whose sums are all equal. Example 1:Input: nums = [4, 3, 2, 3,...
閱讀 1826·2021-10-18 13:30
閱讀 2701·2021-10-09 10:02
閱讀 3050·2021-09-28 09:35
閱讀 2147·2019-08-26 13:39
閱讀 3589·2019-08-26 13:36
閱讀 2011·2019-08-26 11:46
閱讀 1194·2019-08-23 14:56
閱讀 1778·2019-08-23 10:38
