c++ - lower_bound() 返回最后一个元素

Question

当我解决392.Is Subsequence的问题时.在 Leetcode 上。

当我使用 lower_bound() 函数时，我无法理解我想找到最后一个元素和找不到然后返回最后一个元素之间的区别。

这是我的代码:

class Solution {
public:
    bool isSubsequence(string s, string t) {
        vector<vector<int>> temp(26);
        for (int i = 0; i < t.length(); ++i)
            temp[t[i]-'a'].push_back(i);
        int index = -1;
        for (int i = 0; i < s.length(); ++i) {
            auto it = upper_bound(temp[s[i]-'a'].begin(), temp[s[i]-'a'].end(), index);

            //if the last element is we want to find what will happen?
            if (it == temp[s[i]-'a'].end()) return false;
            index = *it;
        }
        return true;
    }
};

如果最后一个元素是我们要查找会发生什么？

Answer 1

end()不指向最后一个元素，它指向 beyond 最后一个元素。强调我的:

Returns an iterator to the end (i.e. the element after the last element) of the given container c or array array.

如果最后一个元素是您要查找的元素，lower_bound 将返回 end() - 1