Solution Explanation for Split Array with Equal Sum

This problem asks whether an array can be split into four subarrays with equal sums. The conditions specify that the splits must occur at indices i, j, and k, such that 0 < i < j < k < n.

The solution uses prefix sums to efficiently calculate the sum of subarrays. A prefix sum array s is created where s[i] represents the sum of elements from nums[0] to nums[i-1]. This allows us to calculate the sum of any subarray (l, r) in O(1) time as s[r+1] - s[l].

The algorithm iterates through possible values of j and then checks for valid i and k.

Algorithm:

1. Calculate Prefix Sums: Compute the prefix sum array s.
2. Iterate through j: Iterate from j = 3 to n - 3 (to ensure there are enough elements for four subarrays).
3. Check for Valid i: For each j, iterate through possible values of i from 1 to j - 1. Check if the sum of the first subarray (0, i - 1) is equal to the sum of the second subarray (i + 1, j - 1). If it is, store this sum in a seen set. This optimization avoids redundant checks.
4. Check for Valid k: For each j and for each potential i (where the sums are equal), iterate through possible values of k from j + 2 to n - 1. Check if the sum of the third subarray (j + 1, k - 1) is equal to the sum of the fourth subarray (k + 1, n - 1) and also if this sum is present in the seen set.
5. Return True: If such i, j, and k are found, return true. Otherwise, return false after checking all possibilities.

Time Complexity Analysis:

The outer loop iterates O(n) times. The nested loops iterate up to O(n) times each. Therefore, the overall time complexity is O(n³). The use of a set (seen in Python, HashSet in Java, unordered_set in C++, map in Go) for checking previously seen sums slightly improves the efficiency but doesn't change the overall time complexity order.

Space Complexity Analysis:

The space complexity is O(n) due to the prefix sum array s and the seen set (whose size can be at most O(n) in the worst case).

Code Explanation (Python):

class Solution:
    def splitArray(self, nums: List[int]) -> bool:
        n = len(nums)
        s = [0] * (n + 1)  # Prefix sum array
        for i, v in enumerate(nums):
            s[i + 1] = s[i] + v
        for j in range(3, n - 3):  # Iterate through possible j values
            seen = set()  # Set to store sums of first two subarrays
            for i in range(1, j - 1):  # Iterate through possible i values
                if s[i] == s[j] - s[i + 1]:  # Check if sum(0,i-1) == sum(i+1,j-1)
                    seen.add(s[i])  # Store the sum if equal
            for k in range(j + 2, n - 1):  # Iterate through possible k values
                if s[n] - s[k + 1] == s[k] - s[j + 1] and s[n] - s[k + 1] in seen:
                    # Check if sum(j+1,k-1) == sum(k+1,n-1) and the sum is in 'seen'
                    return True  # Found a valid split
        return False  # No valid split found
 

The code in other languages (Java, C++, Go) follows the same logic with minor syntactic differences to accommodate each language's features. The core algorithm remains consistent.