牛客补题目

牛客补题
https://ac.nowcoder.com/acm/contest/84528/C
刚开始的思路是对的，这个一定是要用前缀和的。但是后面的代码时间复杂度on方。我把变量赋值在for里面，每次都是从原来的地方开始。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
using ll = long long;
ll a[N], pre[N];
int main()
{
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++)
  {
    cin >> a[i];
    pre[i] = a[i] + pre[i - 1];
  }
  // 前缀和了
  ll count = 0;
  // for (int i = 1; i <= n - 2; i++)
  // {
  //   for (int j = i + 1; j < n; j++)
  //   {
  //     ll a = pre[i]; // 1-i和
  //     ll b = pre[j] - pre[i];
  //     ll c = pre[n] - pre[j];
  //     if (a < b && b > c)
  //     {
  //       count++;
  //     }
  //   }
  // }
  int i = 1;
  int j = 2;
  // i 和j要变为全局变量 这样才能控制时间复杂度。
  //i等于1的时候 j从2开始 如果符合 那么就直接加上去
  for (; i < n; i++)
  {
    for (; j < n; j++)
    {
      ll a = pre[i];
      ll b = pre[j] - pre[i];
      ll c = pre[n] - pre[j];
      if (a < b && b > c)
      {
        count += n - j;
        break;
      }
    }
  }
  cout << count;
}