问答

当前位置

LintCode 138. Subarray Sum

  • Ta: 李助教

想請問助教 我使用C++ STL中的set<> 來儲存 prefixsum 的值,
並在遍歷數組的過程中, 使用set自帶的lower_bound函數來檢查是否有相等的前綴和, 若有則回傳解.

檢查過多次代碼覺得沒錯, 但就是不能AC, 想請助教幫忙
感激不盡!
以下是我的代碼:

class Solution {
public:

class Itm {
public:
    int sum;
    int ith;
    Itm(int s, int i) : sum(s), ith(i) {}
    bool operator < (const Itm & obj) const {
        if (sum != obj.sum) {
            return sum < obj.sum;
        }
        return ith < obj.ith;
    }
};

vector<int> subarraySum(vector<int> &nums) {
    set<Itm> prefix;
    prefix.insert(Itm(0, 0));

    int sum = 0;
    for (int i = 0; i < nums.size(); ++i) {
        sum += nums[i];
        Itm cur(sum, i + 1);

        auto iter = prefix.lower_bound(cur);

        if (iter != prefix.end() && iter->sum == sum) {
            return {iter->ith, i};
        }

        prefix.insert(cur);
    }

    return {0, 0};
}

};

3 个回复

2019-09-09 carry

你的思路没问题,但是你在这一行下面auto iter = prefix.lower_bound(cur);打印一下cur.sum,iter -> sum,iter -> ith,prefix.end(),你可以发现它的值和你的思路的预期并不一样,所以它根本不会进入那个if判断语句,每次都是return {0, 0};


2019-09-10 Phenix

我的疑問就是这一行: auto iter = prefix.lower_bound(cur);打印一下cur.sum,iter -> sum,iter -> ith,prefix.end(), 它的值和為什麼會和预期并不一样?


2019-09-11 carry

auto iter = prefix.lower_bound(cur);这行的原因,prefix这个set里数据类型是你自定义的,他的lower_bound不能正确获取,和平常set里是int的时候一样,你可以直接用map来存,key用下标,value等于前缀和。

我来回答

您没有权限

为提高问答质量,问答版块发言权限只向九章学员开放

登录 注册

© Jiu Zhang 2013-. All rights reserved. 京ICP备16004690号-1