前缀和刷题-- LeetCode

寻找数组的中心下标

题目

题解

1. 预处理前缀和和后缀和数组，注意边界问题，f(0) = 0,g(n-1) = 0
2. 然后遍历数组一遍，f[i] == g[i],i就是下标
3. 时间复杂度是：O(N)

代码

class Solution 
{
public:
    int pivotIndex(vector<int>& nums) 
    {
        int n = nums.size();
        vector<int> f(n);
        vector<int> g(n);
        
        // 数组是0 - n-1,dp数组是1 - n-1,注意控制边界问题
        // 预处理前缀和数组
        for(int i = 1;i < n;i++) f[i] = f[i-1] + nums[i-1];
        // 预处理后缀和数组
        for(int i = n-2;i >= 0;i--) g[i] = g[i+1] + nums[i+1];

        for(int i = 0;i < n;i++)
        {
            if(f[i] == g[i]) return i;
        }

        return -1;
    }
};

巧克力

题目

题解

1. 一定要开long long，被卡数据了
2. 先预处里一个前缀和和后缀和数组，定义一个left和right，去找前缀和后缀相等的数，并且要求最大值
3. 如果左边大扩大后缀和数组，如果右边大扩大前缀和数组

代码

#include <iostream>
#include<algorithm>
using namespace std;

const int N = 2e5 + 10;
long long a[N+1], b[N+1];
int c[N+1];

int main()
{
    int n;
    cin >> n;


    for (int i = 1; i <= n; i++) cin >> c[i];

    for (int i = 1; i <= n; i++) a[i] = a[i - 1] + c[i];
    for (int i = n; i >= 1; i--) b[i] = b[i + 1] + c[i];

    long long m = 0;
    int left = 0,right = n+1;
    while(left < right)
    {
      if(a[left] == b[right])
      {
        if(a[left] > m) m = a[left];
        left++;
        right--;
      }
      else if(a[left] > b[right]) right--;
      else left++;
    }
    cout << m << '\n'; 

    return 0;
}