寻找数组的中心下标

题目

题解

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;
}