如何实现O(n)算法，统计数组中以3开头以7结尾的子集数量

给定每个元素均为数字的数组，要求统计其中所有以3开头、以7结尾的连续子集的总数量。

示例说明 #

给定数组：1,2,5,3,6,7,3,3,7,0,3,4,9,7,8
符合要求的子集总数为8，具体子集如下（仅需统计数量无需输出子集）：

3,6,7
3,6,7,3,3,7
3,6,7,3,3,7,0,3,4,9,7
3,3,7
3,3,7,0,3,4,9,7
3,7
3,7,0,3,4,9,7
3,4,9,7

需求说明 #

现有如下代码框架，需要填充int o_n_alg(int arr[], int size)函数的逻辑，要求算法时间复杂度为O(n)：

int o_n_alg(int arr[], int size)
{
  // To fill with O(n) Algorithm
}

int main(){
   int size = 1000000;
   int *array = new int[size];
   int ans_n;

   for (int i = 0; i < size; i++) 
     cin >> array[i];


   ans_n = o_n_alg(array, size);
}

仅需一次遍历即可完成统计，逻辑如下：

• 维护两个变量：count_3 记录遍历到当前位置之前遇到的数字3的总个数，res 记录最终符合要求的子集总数
• 遍历数组的每个元素：
  • 如果当前元素是3，直接给count_3加1
  • 如果当前元素是7，说明这个7可以和之前出现的所有3分别组成符合要求的连续子集，直接把count_3的值累加到res上
  • 其他元素无需做任何处理
• 遍历结束后返回res即可

该思路时间复杂度为O(n)，空间复杂度为O(1)，完全符合要求。代入示例验证：三个7分别出现时，前面的3的个数分别为1、3、4，累加结果为1+3+4=8，和示例结果完全匹配。

int o_n_alg(int arr[], int size)
{
    int count_3 = 0;
    int res = 0;
    for (int i = 0; i < size; i++) {
        if (arr[i] == 3) {
            count_3++;
        } else if (arr[i] == 7) {
            res += count_3;
        }
    }
    return res;
}

内容的提问来源于stack exchange，提问作者Anıl