如何不使用嵌套循环统计1~n中两不同数和为k的不重复对数？

给定范围1~n的整数和数字k，需统计其中两个不同数相加等于k的可能方式数量，且(A,B)与(B,A)视为同一种情况。当前实现采用嵌套循环，效率较低，询问是否可不使用嵌套循环实现。

现有嵌套循环代码 #

n, k = int(input()), int(input())
cnt = 0
for i in range(1, n+1):
    for s in range(1, n+1):
        if i == 1 and s == 1 or i == n+1 and s==n+1:
            pass
        else:
            if i+s==k:
                cnt += 1
print(int(cnt/2))

示例输入输出 #

• 输入：

8
5

• 解释：符合条件的数对为(1,4)和(2,3)，输出应为2。

无需嵌套循环的实现方案 #

方案1：数学计算法（O(1)时间复杂度） #

核心思路是直接推导有效数对的范围：
要找满足 a + b = k 且 1 ≤ a < b ≤ n 的数对，需满足：

1. a < b → a < k - a → a < k/2
2. b = k - a ≤ n → a ≥ k - n
3. a ≥ 1

综合得到a的有效范围是 max(1, k - n) ≤ a < k/2，统计这个区间内的整数个数即为结果。

代码实现：

n, k = int(input()), int(input())
min_a = max(1, k - n)
max_a = (k - 1) // 2  # 确保a严格小于k/2
count = max(0, max_a - min_a + 1)
print(count)

方案2：单循环遍历（O(n)时间复杂度） #

遍历每个a，计算对应的b = k - a，只需检查b是否满足b > a且b ≤ n，满足则计数加1。

代码实现：

n, k = int(input()), int(input())
cnt = 0
for a in range(1, n+1):
    b = k - a
    if b > a and b <= n:
        cnt += 1
print(cnt)

这两种方案都避免了嵌套循环，效率远高于原实现，其中数学计算法的效率最优。

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