LeetCode 75| 前缀和
目录
1732 找到最高海拔
724 找到数组的中心下标
1732 找到最高海拔
class Solution {
public:int largestAltitude(vector<int>& gain) {int res = 0;int sum = 0;for(int num : gain){sum += num;res = max(res,sum);}return res;}
};时间复杂度O(n)
空间复杂度O(1)
724 找到数组的中心下标
在循环中注意i不参与运算，需要将nums[i]排除
class Solution {
public:int pivotIndex(vector<int>& nums) {int rsum = 0;int lsum = 0;rsum = accumulate(nums.begin(),nums.end(),0);for(int i = 0;i < nums.size();i++){rsum -= nums[i];if(lsum == rsum)return i;lsum += nums[i];}return -1;}
};时间复杂度O(n)
空间复杂度O(1)