题目

思路和解题方法

方案一——遍历+哈希

仅能过60%样例,大多数同学都用的该方法,就不过多赘述

#include <iostream>
#include <unordered_map&gt;
using namespace std;
int main()
{

  string s;
  cin &gt;&gt; s;
  int n = s.size();
  int res = n;
  for (int i = 0; i < n; ++i) {
    unordered_map<char, int&gt; m;
      ++m[s[i]];
    for (int j = i + 1; j < n; ++j) {
      ++m[s[j]];
      res += m.size();
    }
  }
  cout << res;
  return 0;
}

代码
#include <iostream&gt;
#include <stdlib.h&gt;
#include <cstring&gt;
using namespace std;
int main()
{
    long long int i, n, sum = 0; // 声明变量 i,n,sum,并初始化 sum 为 0
    char a[1000000]; // 声明个字符数组 a,用于存储输入的字符串,数组大小为 1000000
    int s[26] = {0}; // 声明一个长度为 26 的整型数组 s,用于记录每个小写字母最后一次出现的位置

    cin&gt;&gt;a; // 输入字符串到数组 a 中
    n = strlen(a); // 获取字符串 a 的长度

    for(i = 0; i < n; i++) // 遍历字符串 a
    {
        sum += (i+1-s[a[i]-'a']) * (n-i); // 根据公式更新 sum 的值
        s[a[i] - 'a'] = i+1; // 更新数组 s 中对应字母的位置信息
    }

    cout<<sum<<endl; // 输出最终计算得到的结果 sum
    return 0;
}

复杂度

        时间复杂度:

                O(n)

时间复杂度

        空间复杂

                O(1)

空间复杂度:

总结起来,这段代码的时间复杂度为 O(n),空间复杂度为 O(1)。

觉得有用的话可以点赞支持一下。

如果愿意的话关注一下。会对你有更多的帮助。

每天都会不定更新哦  >人<  。

原文地址:https://blog.csdn.net/jgk666666/article/details/134733446

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任

如若转载,请注明出处:http://www.7code.cn/show_31624.html

如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注