Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 548 with 16 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 548 # by problem number
lcpy gen -s split_array_with_equal_sum # by problem name
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(0, i - 1), (i + 1, j - 1), (j + 1, k - 1) and (k + 1, n - 1) is equal.(l, r) represents a slice of the original array starting from the element indexed l to the element indexed r.
Input: nums = [1,2,1,2,1,2,1]
Output: true
Explanation:
i = 1, j = 3, k = 5.
sum(0, i - 1) = sum(0, 0) = 1
sum(i + 1, j - 1) = sum(2, 2) = 1
sum(j + 1, k - 1) = sum(4, 4) = 1
sum(k + 1, n - 1) = sum(6, 6) = 1
Input: nums = [1,2,1,2,1,2,1,2]
Output: false
n == nums.length1 <= n <= 2000-10^6 <= nums[i] <= 10^6class Solution:
# Time: O(n^2)
# Space: O(n)
def split_array(self, nums: list[int]) -> bool:
n = len(nums)
prefix = [0] * (n + 1)
for i, value in enumerate(nums):
prefix[i + 1] = prefix[i] + value
for j in range(3, n - 3):
left_sums: set[int] = set()
for i in range(1, j - 1):
if prefix[i] == prefix[j] - prefix[i + 1]:
left_sums.add(prefix[i])
for k in range(j + 2, n - 1):
s3 = prefix[k] - prefix[j + 1]
s4 = prefix[n] - prefix[k + 1]
if s3 == s4 and s3 in left_sums:
return True
return False
| Time | Space |
|---|---|
| O(n^2) | O(n) |