给定一个std::vector按升序排序的不同元素，我想开发一种算法来确定集合中是否有两个元素的总和为某个值，sum。
我已经尝试了两种不同的方法，并进行了各自的权衡：
我可以扫描整个向量，对于向量中的每个元素，对向量应用二分搜索 ( std::lower_bound) 以搜索sum与当前元素之间的差异对应的元素。这是一个不需要额外空间的 O(n log n) 时间解决方案。
我可以遍历整个向量并填充std::unordered_set. 然后，我扫描向量，对于每个元素，我在 中查找与当前元素std::unordered_set之间的差异sum。由于对哈希表的搜索平均以恒定时间运行，因此该解决方案以线性时间运行。但是，由于std::unordered_set数据结构的原因，此解决方案需要额外的线性空间。
尽管如此，我正在寻找一种在线性时间内运行且不需要额外线性空间的解决方案。有任何想法吗？似乎我被迫用速度换取空间。
我们知道jal指定了一个 21 位的偏移量。但是，它不编码 21 位偏移量而是编码 20 位偏移量。原因是地址的最低有效位始终为零，因为最小可能的 RISC-V 指令是 2 个字节，因此该位未在指令中编码。
通过以这种方式对偏移进行编码，它可以提供 ±1MiB 的跳跃范围。如果jal确实对 LSB 进行编码，它将仅提供 ±512KiB 的跳跃范围。
但是，jalr指定 12 位偏移量的指令确实对 LSB 进行了编码。这将跳跃范围减少到 ±2kiB（而不是 ±4kiB）。我知道它jalr使用 I 型格式，它与addi此类指令的立即数的 LSB 必须编码相同。但是，我认为没有理由必须对jalr.