|
| 1 | +packagecom.stevesun.solutions; |
| 2 | + |
| 3 | +importjava.util.HashSet; |
| 4 | + |
| 5 | +/** |
| 6 | + * Given an array with n integers, you need to find if there are triplets (i, j, k) which satisfies following conditions: |
| 7 | +
|
| 8 | + 0 < i, i + 1 < j, j + 1 < k < n - 1 |
| 9 | + Sum of subarrays (0, i - 1), (i + 1, j - 1), (j + 1, k - 1) and (k + 1, n - 1) should be equal. |
| 10 | + 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. |
| 11 | +
|
| 12 | + Example: |
| 13 | + Input: [1,2,1,2,1,2,1] |
| 14 | + Output: True |
| 15 | + Explanation: |
| 16 | + i = 1, j = 3, k = 5. |
| 17 | + sum(0, i - 1) = sum(0, 0) = 1 |
| 18 | + sum(i + 1, j - 1) = sum(2, 2) = 1 |
| 19 | + sum(j + 1, k - 1) = sum(4, 4) = 1 |
| 20 | + sum(k + 1, n - 1) = sum(6, 6) = 1 |
| 21 | +
|
| 22 | + Note: |
| 23 | + 1 <= n <= 2000. |
| 24 | + Elements in the given array will be in range [-1,000,000, 1,000,000]. |
| 25 | + */ |
| 26 | +publicclassSplitArraywithEqualSum { |
| 27 | + |
| 28 | +publicbooleansplitArray_O_N_3(int[]nums) {//TODO: this one is failed by test4, probably some index wrong |
| 29 | +if (nums ==null ||nums.length ==0)returnfalse; |
| 30 | +long[]previousSums =newlong[nums.length+1]; |
| 31 | +for (inti =1;i <=nums.length;i++) { |
| 32 | +previousSums[i] =previousSums[i-1] +nums[i-1]; |
| 33 | + } |
| 34 | + |
| 35 | +intn =nums.length; |
| 36 | +for (inti =1;i <=n-6;i++) { |
| 37 | +longsum1 =previousSums[i] -previousSums[0]; |
| 38 | +for (intj =i+2;j <=n-4;j++) { |
| 39 | +longsum2 =previousSums[j] -previousSums[i+1]; |
| 40 | +if (sum1 !=sum2)break; |
| 41 | +for (intk =j+2;k <=n-2;k++) { |
| 42 | +longsum3 =previousSums[k] -previousSums[j+1]; |
| 43 | +if (sum2 !=sum3)break; |
| 44 | +longsum4 =previousSums[n] -previousSums[k+1]; |
| 45 | +if (sum3 ==sum4)returntrue; |
| 46 | + } |
| 47 | + } |
| 48 | + } |
| 49 | +returnfalse; |
| 50 | + } |
| 51 | + |
| 52 | +publicbooleansplitArray_O_N_2(int[]nums) { |
| 53 | +if (nums.length <7) |
| 54 | +returnfalse; |
| 55 | +int[]sum =newint[nums.length]; |
| 56 | +sum[0] =nums[0]; |
| 57 | +for (inti =1;i <nums.length;i++) { |
| 58 | +sum[i] =sum[i -1] +nums[i]; |
| 59 | + } |
| 60 | +for (intj =3;j <nums.length -3;j++) { |
| 61 | +HashSet<Integer>set =newHashSet<>(); |
| 62 | +for (inti =1;i <j -1;i++) { |
| 63 | +if (sum[i -1] ==sum[j -1] -sum[i]) |
| 64 | +set.add(sum[i -1]); |
| 65 | + } |
| 66 | +for (intk =j +2;k <nums.length -1;k++) { |
| 67 | +if (sum[nums.length -1] -sum[k] ==sum[k -1] -sum[j] &&set.contains(sum[k -1] -sum[j])) |
| 68 | +returntrue; |
| 69 | + } |
| 70 | + } |
| 71 | +returnfalse; |
| 72 | + } |
| 73 | + |
| 74 | +} |