Solution

Method 1 – Prefix Sum and Hash Set

Intuition

We want to find three split points (i, j, k) such that the sums of four subarrays are equal. By using prefix sums, we can efficiently compute subarray sums and use a hash set to track possible sums for the first two splits, then check for a matching sum in the third split.

Approach

Compute the prefix sum array for nums.
For each possible j (from 3 to n-4), try all possible i (from 1 to j-2) and store valid sums in a set.
For each possible k (from j+2 to n-2), check if the sum for the third split matches any sum in the set.
If a match is found, return true.
If no match is found after all iterations, return false.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    bool splitArray(vector<int>& nums) {\n        int n = nums.size();\n        vector<int> pre(n+1, 0);\n        for (int i = 0; i < n; ++i) pre[i+1] = pre[i] + nums[i];\n        for (int j = 3; j < n-3; ++j) {\n            unordered_set<int> s;\n            for (int i = 1; i < j-1; ++i) {\n                int sum1 = pre[i];\n                int sum2 = pre[j] - pre[i+1];\n                if (sum1 == sum2) s.insert(sum1);\n            }\n            for (int k = j+2; k < n-1; ++k) {\n                int sum3 = pre[k] - pre[j+1];\n                int sum4 = pre[n] - pre[k+1];\n                if (sum3 == sum4 && s.count(sum3)) return true;\n            }\n        }\n        return false;\n    }\n};","lang":"cpp"},{"language":"Go","code":"func splitArray(nums []int) bool {\n    n := len(nums)\n    pre := make([]int, n+1)\n    for i := 0; i < n; i++ {\n        pre[i+1] = pre[i] + nums[i]\n    }\n    for j := 3; j < n-3; j++ {\n        s := map[int]struct{}{}\n        for i := 1; i < j-1; i++ {\n            sum1 := pre[i]\n            sum2 := pre[j] - pre[i+1]\n            if sum1 == sum2 {\n                s[sum1] = struct{}{}\n            }\n        }\n        for k := j+2; k < n-1; k++ {\n            sum3 := pre[k] - pre[j+1]\n            sum4 := pre[n] - pre[k+1]\n            if sum3 == sum4 {\n                if _, ok := s[sum3]; ok {\n                    return true\n                }\n            }\n        }\n    }\n    return false\n}","lang":"go"},{"language":"Java","code":"class Solution {\n    public boolean splitArray(int[] nums) {\n        int n = nums.length;\n        int[] pre = new int[n+1];\n        for (int i = 0; i < n; ++i) pre[i+1] = pre[i] + nums[i];\n        for (int j = 3; j < n-3; ++j) {\n            Set<Integer> s = new HashSet<>();\n            for (int i = 1; i < j-1; ++i) {\n                int sum1 = pre[i];\n                int sum2 = pre[j] - pre[i+1];\n                if (sum1 == sum2) s.add(sum1);\n            }\n            for (int k = j+2; k < n-1; ++k) {\n                int sum3 = pre[k] - pre[j+1];\n                int sum4 = pre[n] - pre[k+1];\n                if (sum3 == sum4 && s.contains(sum3)) return true;\n            }\n        }\n        return false;\n    }\n}","lang":"java"},{"language":"Kotlin","code":"class Solution {\n    fun splitArray(nums: IntArray): Boolean {\n        val n = nums.size\n        val pre = IntArray(n+1)\n        for (i in 0 until n) pre[i+1] = pre[i] + nums[i]\n        for (j in 3 until n-3) {\n            val s = mutableSetOf<Int>()\n            for (i in 1 until j-1) {\n                val sum1 = pre[i]\n                val sum2 = pre[j] - pre[i+1]\n                if (sum1 == sum2) s.add(sum1)\n            }\n            for (k in j+2 until n-1) {\n                val sum3 = pre[k] - pre[j+1]\n                val sum4 = pre[n] - pre[k+1]\n                if (sum3 == sum4 && s.contains(sum3)) return true\n            }\n        }\n        return false\n    }\n}

Related Tags