这是我创建的子字符串的问题。我想知道如何实现这个问题的O(nlog(n))解决方案，因为这种天真的方法非常简单。事情是这样的。您有一个字符串S。CCD_ 3有许多子串。在某些子字符串中，第一个字符和最后一个字符不止一次出现。查找第一个和最后一个字符不止一次出现的子字符串的数量。
Input: "ABCDCBE"
Expected output: 2
Explanation: "BCDCB" and "CDC" are two such substrings
该测试用例解释只有"；BCDCB"；以及"；CDC"；其中第一个字符和最后一个字符相同。
除了具有"；ABABCAC"；是第一个字符"所在的子串；A"；出现3次，最后一个字符"；C"；出现两次"AAAABB"；也是另一个子字符串。
"AAAAB"；不满足。
我学到的是O(nlog(n))，它可能对解决方案有贡献，也可能没有贡献。二进制索引树可以用来解决这个问题。还有排序和二进制搜索，但首先我想特别关注二进制索引树。
我正在寻找O(n log(n))或更好的空间复杂性。
UTF-16 中也有字符
我的解决方案要点如下：
对输入数组进行迭代，并为每个位置计算在该位置结束的"有效"子字符串的数量。这些值的总和就是有效子字符串的总量。我们通过使用二进制索引树计算当前位置之前的子字符串的有效起始数量来实现这一点。
现在查看完整的细节：
当我们在数组上迭代时，我们认为当前元素是子字符串的末尾，我们说，有效开始的位置是这样的，即它的值再次出现在it和我们当前迭代的位置之间。(即，如果子字符串开头的值至少出现两次(
例如：
current index V
data = [1, 2, 3, 4, 1, 4, 3, 2]
valid = [1, 0, 1, 1, 0, 0, 0, 0]
0 1 2 3 4 5 6 7
第一个1(在索引0处(是有效的开始，因为在它之后但在当前索引(索引6(之前还有另一个1(在索引4处(。
现在，计算当前索引之前的有效开始数量，可以得到与我们想要的非常接近的结果，只是我们可能会获取一些没有两次出现子字符串最后一个值的子字符串(即我们当前正在迭代的那个(
例如：
current index V
data = [1, 2, 3, 4, 1, 4, 3, 2]
valid = [1, 0, 1, 1, 0, 0, 0, 0]
0 1 2 3 4 5 6 7
^--------^
这里，4被标记为有效的开始(因为后面还有另一个4(，但相应的子串没有两个3。
为了解决这个问题，我们将只考虑当前值之前出现的有效启动。(这意味着子字符串将同时包含当前值和它以前的外观，因此，最后一个元素将在子字符串中至少出现两次(
伪代码如下：
fn solve(arr) {
answer := 0
for i from 1 to length(arr) {
previous_index := find_previous(arr, i)
if there is a previous_index {
arr[previous_index].is_valid_start = true
answer += count_valid_starts_up_to_and_including(arr, previous_index)
}
}
return answer
}
为了有效地实现这些操作，我们使用哈希表来查找值的前一个位置，并使用二进制索引树(BIT(来跟踪和计数有效位置。
因此，一个更加充实的伪代码看起来像
fn solve(arr) {
n := length(arr)
prev := hash_table{}
bit := bit_indexed_tree{length = n}
answer := 0
for i from 1 to length(arr) {
value := arr[i]
previous_index := prev[value]
if there is a previous_index {
bit.update(previous_index, 1)
answer += bit.query(previous_index)
}
prev[value] = i
}
return answer
}
最后，由于伪代码并不总是足够的，这里有一个C++实现，其中控制流有点模糊，以确保std::unordered_map(C++的内置哈希表(的有效使用
class Bit {
std::vector<int> m_data;
public:
// initialize BIT of size `n` with all 0s
Bit(int n);
// add `value` to index `i`
void update(int i, int value);
// sum from index 0 to index `i` (inclusive)
int query(int i);
};
long long solve (std::vector<int> const& arr) {
int const n = arr.size();
std::unordered_map<int, int> prev_index;
Bit bit(n);
long long answer = 0;
int i = 0;
for (int value : arr) {
auto insert_result = prev_index.insert({value, i});
if (!insert_result.second) { // there is a previous index
int j = insert_result.first->second;
bit.update(j, 1);
answer += bit.query(j);
insert_result.first->second = i;
}
++i;
}
return answer;
}
编辑：为了透明起见，这里是我用来测试代码的Fenwick树实现
struct Bit {
std::vector<int> m_data;
Bit(int n) : m_data(n+2, 0) { }
int query(int i) {
int res = 0;
for(++i; i > 0; i -= i&-i) res += m_data[i];
return res;
}
void update(int i, int x) {
for(++i; i < m_data.size(); i += i&-i) m_data[i] += x;
}
};