我正在尝试解决 BinarySearch.com 上的一个问题：

给定一个按升序排序的整数 nums 和一个整数 k 的列表，返回列表中的任意两个元素加起来是否为 k。您不能两次使用相同的元素。注意：数字可以是负数或 0。这应该在O(1)空格中完成。
所以对于nums = [1, 3, 5, 8]和k = 6，答案应该是true。

我知道它可以使用两个指针来完成，但我正在学习二进制搜索，所以我想出了以下逻辑：

bool solve(vector<int>& nums, int k) {
    for(int i=0; i<nums.size(); i++) {
        auto loc=lower_bound(begin(nums), end(nums), k-nums[i]);
        if(loc!=nums.end()) {
            if(distance(nums.begin(), loc)!=i && *loc+nums[i]==k) return true;
        }
    }
    return false;
}

它被接受了，但时间复杂度是多少？我不确定是O(NlogN)因为我O(logN)对 中的每个值运行二分搜索（算法）nums，还是应该是O(N^2)因为当if条件为真时，我使用distance()，据我所知，这O(n)本身就是一个操作。

回答