Number of centered subarrays

Array Hash Table Enumeration

66.9% acceptance

Mar 16, 2026

You are given an integer array nums. A subarray of nums is called centered if the sum of its elements is equal to at least one element within that same subarray. Return the number of centered subarrays of nums.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn centered_subarrays(nums: Vec<i32>) -> i32 {
    let n = nums.len();
    let mut count = 0i32;

    // For each subarray [i..=j], check if sum equals any element in it
    // Precompute prefix sums
    let mut prefix = vec![0i64; n + 1];
    for i in 0..n {
      prefix[i + 1] = prefix[i] + nums[i] as i64;
    }

    for i in 0..n {
      for j in i..n {
        let sum = prefix[j + 1] - prefix[i];
        // Check if any element in nums[i..=j] equals sum
        let mut found = false;
        for k in i..=j {
          if nums[k] as i64 == sum {
            found = true;
            break;
          }
        }
        if found {
          count += 1;
        }
      }
    }

    count
  }
}