Skip to content

548. Split Array with Equal Sum

  • Time: $O(n^2)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
 public:
  bool splitArray(vector<int>& nums) {
    const int n = nums.size();
    if (n < 7)
      return false;

    vector<int> prefix(n);

    partial_sum(nums.begin(), nums.end(), prefix.begin());

    for (int j = 3; j < n - 3; ++j) {
      unordered_set<int> seen;
      for (int i = 1; i < j - 1; ++i)
        if (prefix[i - 1] == prefix[j - 1] - prefix[i])
          seen.insert(prefix[i - 1]);
      for (int k = j + 2; k < n - 1; ++k)
        if (prefix[n - 1] - prefix[k] == prefix[k - 1] - prefix[j] &&
            seen.contains(prefix[k - 1] - prefix[j]))
          return true;
    }

    return false;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
  public boolean splitArray(int[] nums) {
    final int n = nums.length;
    if (n < 7)
      return false;

    int[] prefix = new int[n];

    for (int i = 0; i < n; ++i)
      prefix[i] = i == 0 ? nums[0] : prefix[i - 1] + nums[i];

    for (int j = 3; j < n - 3; ++j) {
      HashSet<Integer> seen = new HashSet<>();
      for (int i = 1; i < j - 1; ++i)
        if (prefix[i - 1] == prefix[j - 1] - prefix[i])
          seen.add(prefix[i - 1]);
      for (int k = j + 2; k < n - 1; ++k)
        if (prefix[n - 1] - prefix[k] == prefix[k - 1] - prefix[j] &&
            seen.contains(prefix[k - 1] - prefix[j]))
          return true;
    }

    return false;
  }
}