Split array with equal sum

Array Hash Table Prefix Sum

50.1% acceptance

Mar 31, 2026

418

132

Given an integer array nums of length n, return true if there is a triplet (i, j, k) which satisfies the following conditions: 0 < i, i + 1 < j, j + 1 < k < n - 1 The sum of subarrays (0, i - 1), (i + 1, j - 1), (j + 1, k - 1) and (k + 1, n - 1) is equal. A subarray (l, r) represents a slice of the original array starting from the element indexed l to the element indexed r.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn split_array(nums: Vec<i32>) -> bool {
    use std::collections::HashSet;
    let n = nums.len();
    if n < 7 { return false; }
    let mut prefix = vec![0i64; n + 1];
    for i in 0..n {
      prefix[i + 1] = prefix[i] + nums[i] as i64;
    }
    // For each j, find if there exist i and k such that all 4 parts are equal
    for j in 3..n - 3 {
      let mut set = HashSet::new();
      // Try all valid i for this j
      for i in 1..j - 1 {
        let s1 = prefix[i];
        let s2 = prefix[j] - prefix[i + 1];
        if s1 == s2 {
          set.insert(s1);
        }
      }
      // Try all valid k for this j
      for k in j + 2..n - 1 {
        let s3 = prefix[k] - prefix[j + 1];
        let s4 = prefix[n] - prefix[k + 1];
        if s3 == s4 && set.contains(&s3) {
          return true;
        }
      }
    }
    false
  }
}