Skip to content

3804. Number of Centered Subarrays

Description

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.

 

Example 1:

Input: nums = [-1,1,0]

Output: 5

Explanation:

  • All single-element subarrays ([-1], [1], [0]) are centered.
  • The subarray [1, 0] has a sum of 1, which is present in the subarray.
  • The subarray [-1, 1, 0] has a sum of 0, which is present in the subarray.
  • Thus, the answer is 5.

Example 2:

Input: nums = [2,-3]

Output: 2

Explanation:

Only single-element subarrays ([2], [-3]) are centered.

 

Constraints:

  • 1 <= nums.length <= 500
  • -105 <= nums[i] <= 105

Solutions

Solution 1: Hash Table + Enumeration

Thinking

A centered subarray has sum equal to one of its elements. \(n \le 500\) makes a triple loop with a linear search heavier than needed.

Fixing the left endpoint and extending right lets both the sum and the value set grow incrementally.

We enumerate start \(i\), maintain running sum \(s\) and a hash set of \(nums[i..j]\), and count when \(s\) appears in the set.

All \(O(n^2)\) subarrays are visited; the hash test makes the inner check amortized constant time.

We enumerate all starting indices \(i\) of subarrays, then starting from index \(i\), we enumerate the ending index \(j\) of the subarray, calculate the sum \(s\) of elements in the subarray \(nums[i \ldots j]\), and add all elements in the subarray to the hash table \(\textit{st}\). After each enumeration, we check if \(s\) appears in the hash table \(\textit{st}\). If it does, it means the subarray \(nums[i \ldots j]\) is a centered subarray, and we increment the answer by \(1\).

The time complexity is \(O(n^2)\) and the space complexity is \(O(n)\), where \(n\) is the length of the array \(nums\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def centeredSubarrays(self, nums: List[int]) -> int:
        n = len(nums)
        ans = 0
        for i in range(n):
            st = set()
            s = 0
            for j in range(i, n):
                s += nums[j]
                st.add(nums[j])
                if s in st:
                    ans += 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
    public int centeredSubarrays(int[] nums) {
        int n = nums.length;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            Set<Integer> st = new HashSet<>();
            int s = 0;
            for (int j = i; j < n; j++) {
                s += nums[j];
                st.add(nums[j]);
                if (st.contains(s)) {
                    ans++;
                }
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int centeredSubarrays(vector<int>& nums) {
        int n = nums.size();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            unordered_set<int> st;
            int s = 0;
            for (int j = i; j < n; j++) {
                s += nums[j];
                st.insert(nums[j]);
                if (st.count(s)) {
                    ans++;
                }
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
func centeredSubarrays(nums []int) int {
    n := len(nums)
    ans := 0
    for i := 0; i < n; i++ {
        st := make(map[int]struct{})
        s := 0
        for j := i; j < n; j++ {
            s += nums[j]
            st[nums[j]] = struct{}{}
            if _, ok := st[s]; ok {
                ans++
            }
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
function centeredSubarrays(nums: number[]): number {
    const n = nums.length;
    let ans = 0;
    for (let i = 0; i < n; i++) {
        const st = new Set<number>();
        let s = 0;
        for (let j = i; j < n; j++) {
            s += nums[j];
            st.add(nums[j]);
            if (st.has(s)) {
                ans++;
            }
        }
    }
    return ans;
}

Comments