求O(n²)复杂度算法判断升序实数组各元素是否为两数之和

解法思路 #

利用数组已升序排序的特性，对每一个待判断的元素M[k]，仅需要在它前面（含自身）的子数组范围内用双指针法搜索是否存在两个元素之和等于M[k]即可。每一轮双指针搜索的时间复杂度为O(k)，整体总时间复杂度为O(n²)，完全符合要求。

伪代码实现 #

输入：升序排序的实数数组 M，长度为 n
输出：布尔数组 is_composable，长度为 n，is_composable[k] 表示 M[k] 是否为可合成数

// 初始化结果数组全为false
for k from 0 to n-1:
    is_composable[k] = false

// 逐个判断每个元素
for k from 0 to n-1:
    left = 0
    right = k  // 允许s和t为同一个元素，若要求s≠t可改为right = k-1
    while left <= right:
        sum = M[left] + M[right]
        if sum == M[k]:
            is_composable[k] = true
            break  // 找到一组符合要求的数即可停止搜索
        elif sum < M[k]:
            left = left + 1  // 和太小，左指针右移增大和
        else:
            right = right - 1  // 和太大，右指针左移减小和

return is_composable

补充说明 #

• 如果题目要求s和t必须是不同的元素，只需要把right的初始值改为k-1，同时循环条件改为left < right即可。
• 因为数组元素是实数，判断相等时如果存在浮点精度问题，可以将相等判断替换为abs(sum - M[k]) < 精度阈值的逻辑，阈值可根据实际场景设置为1e-9等值。

内容的提问来源于stack exchange，提问作者Marvin Bundschuh