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)