算法基础

前缀和

CF1426D：给一个长为n的序列，求至少插入几个数，使得连续子序列的和均不为0

解：求前缀和，若出现2个相等的前缀和prefix[i]、prefix[j]，则说明i-1到j之间的数和为0

// Copyright (c) 2021, Jiang Yinzuo. All rights reserved.

#include <cstdio>
#include <unordered_set>
using std::unordered_set;

long long a[200009];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%lld", a + i);
    }

    unordered_set<long long> prefixs;
    prefixs.insert(0);
    long long prefix = 0;
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        prefix += a[i];
        if (prefixs.find(prefix) != prefixs.end()) {
            ++ans;
            prefixs.clear();
            prefix = a[i];
            prefixs.insert(0);
        }
        prefixs.insert(prefix);
    }
    printf("%d\n", ans);
    return 0;
}

双指针

Leetcode 盛水最多的容器