leetcode
leetcode 2451 ~ 2500
子数组不同元素数目的平方和 II

子数组不同元素数目的平方和 II

难度:

标签:

题目描述

You are given a 0-indexed integer array nums.

The distinct count of a subarray of nums is defined as:

  • Let nums[i..j] be a subarray of nums consisting of all the indices from i to j such that 0 <= i <= j < nums.length. Then the number of distinct values in nums[i..j] is called the distinct count of nums[i..j].

Return the sum of the squares of distinct counts of all subarrays of nums.

Since the answer may be very large, return it modulo 109 + 7.

A subarray is a contiguous non-empty sequence of elements within an array.

 

Example 1:

Input: nums = [1,2,1]
Output: 15
Explanation: Six possible subarrays are:
[1]: 1 distinct value
[2]: 1 distinct value
[1]: 1 distinct value
[1,2]: 2 distinct values
[2,1]: 2 distinct values
[1,2,1]: 2 distinct values
The sum of the squares of the distinct counts in all subarrays is equal to 12 + 12 + 12 + 22 + 22 + 22 = 15.

Example 2:

Input: nums = [2,2]
Output: 3
Explanation: Three possible subarrays are:
[2]: 1 distinct value
[2]: 1 distinct value
[2,2]: 1 distinct value
The sum of the squares of the distinct counts in all subarrays is equal to 12 + 12 + 12 = 3.

 

Constraints:

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

代码结果

运行时间: 3006 ms, 内存: 87.3 MB

/*
 * 题目思路：
 * 使用Java Stream和集合类来计算所有子数组的不同计数值的平方和。
 * 将滑动窗口和哈希表的逻辑用Java Stream表示出来，
 * 并且使用Stream API来处理数组和集合。
 */

import java.util.*;
import java.util.stream.Collectors;

public class Solution {
    public int sumOfSquaredDistinctCounts(int[] nums) {
        int n = nums.length;
        int MOD = 1000000007;
        long result = 0;

        for (int i = 0; i < n; i++) {
            Set<Integer> distinctElements = new HashSet<>();
            for (int j = i; j < n; j++) {
                distinctElements.add(nums[j]);
                int distinctCount = distinctElements.size();
                result = (result + (long) distinctCount * distinctCount) % MOD;
            }
        }

        return (int) result;
    }
}

解释

方法:

该题解采用了线段树结合延迟更新的技巧来处理子数组不同元素数目的计算。首先，线段树用于高效地管理和更新子数组的不同元素数目。延迟更新机制用于在必要时批量更新子数组信息，以提高效率。算法的核心在于维护每个元素最后一次出现的位置，并使用线段树在每次遍历新元素时，更新该元素之后的所有子数组的不同元素计数。这样，每遍历一个新元素，就可以计算出以该元素结尾的所有子数组的不同元素计数增量，并累加到结果中。

时间复杂度:

O(n log n)

空间复杂度:

O(n)

代码细节讲解

🦆
在实现线段树时，你是如何选择线段树大小为数组长度的四倍的？这样的大小是否总是足够或有时过度？
▷
线段树作为一种二叉树结构，通常存储在一个数组中。为了确保线段树可以覆盖所有区间的情况，选择其大小为原数组长度的四倍是常见的实践。这是因为在最坏的情况下，线段树可能需要更多的空间来存储所有分割的区间，尤其是当区间被细分到单个元素时。这个大小不仅可以容纳所有区间节点，还包括了必要的父节点和子节点，确保树的完整性和功能的实现。虽然这看起来有时可能过大，但它提供了足够的空间保证，避免了动态调整大小的复杂性，通常线段树的空间复杂度为O(4n)是可以接受的，以换取时间效率。
🦆
你提到了延迟更新（lazy propagation）技术，能否详细解释这种技术在解决此类问题中的具体作用和实现方法？
▷
延迟更新技术（lazy propagation）是优化线段树操作的一种方法，特别适用于大量的区间更新操作。在此题解中，当需要更新一个区间内所有元素的值时，而不立即更新每个单独的元素，延迟更新技术通过标记未完成的更新操作来延迟实际的更新过程。这样，在进行区间查询或需要的时候，才会向下传递这些更新，从而减少不必要的计算量。具体实现中，每个节点会有一个额外的延迟标记数组`lazy`，用于记录该节点下所有子节点需要增加的值。在查询或更新操作中，如果遇到有延迟标记的节点，会先处理这个延迟标记，将其应用到子节点上，并清除当前节点的延迟标记，以保证数据的准确性。这种方法大大提高了效率，尤其是在处理大规模数据时。
🦆
算法中涉及到数组`d`用于记录每个元素最后一次出现的位置，请问这个数组的维护是否会影响整体算法的效率，如果会，如何优化？
▷
数组`d`用于记录每个元素最后一次出现的位置，是解决此问题的关键部分之一。尽管这会增加空间复杂度，并在每次元素出现时更新其值，但这种更新操作的时间复杂度为O(1)，通常不会显著影响算法的整体效率。然而，当元素种类非常多时，维护这样一个数组可能会消耗较多的内存。为优化这一点，可以考虑使用哈希表代替数组来存储元素的最后位置，特别是当元素范围很大或不连续时。哈希表在这种情况下可以节省空间，且仍然保持常数时间的访问和更新效率。

相关问题

美丽塔 I有向图访问计数