LeetCode 75| 前缀和

2023-12-26 12:51:00

目录

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)

文章来源:https://blog.csdn.net/m0_72832574/article/details/135216875
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。