问答

当前位置

LintCode 138. Subarray Sum

  • Ta: 林湖龙

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

檢查過多次代碼覺得沒錯, 但就是不能AC, 經過打印的方式,
發現这一行下面auto iter = prefix.lower_bound(cur);打印一下cur.sum,iter -> sum,iter -> ith,prefix.end(),
发现它的值和我的预期并不一样,所以它根本不会进入那个if判断语句,每次都是return {0, 0};

我的疑問是, 為什麼這一行的行為會和預期不一樣?
是甚麼原因造成的 還請專業的助教幫忙
感激不盡!
以下是我的代碼:

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

};

1 个回复

2019-09-11 carry

Itm中重载“<”的时候,应该直接比较sum的大小就可以了。
目前的写法中,如果后面出现了相同的sum,在目前的“<”的定义中,拥有相同sum的Itm也会小于新来的Itm,因为先加入的Itm-ith总是比较小的。
改成:
```C++
bool operator < (const Itm & obj) const {
return sum < obj.sum;
}
就可以了。

我来回答

您没有权限

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

登录 注册

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