B002排序、双指针、哈希表、两数之和到K数之和（1640~1642）CSES？
摘要：1640 Sum of Two Values - CSES 1641 Sum of Three Values - CSES 1642 Sum of Four Values - CSES 这类问题可以抽象成 (K) 数之和，本质是递归的转
1640 Sum of Two Values - CSES
1641 Sum of Three Values - CSES
1642 Sum of Four Values - CSES
这类问题可以抽象成 \(K\) 数之和，本质是递归的转化为两数之和，时间复杂度为 \(N^{K-1}\) 。一般可以排序双指针或哈希表解决。
题意：给定一个 \(n\) 个整数的数组，找出 \(k\) 个不同位置（1-based）的元素，使其的和等于 \(x\) 。若无解输出 IMPOSSIBLE 。与力扣上的题目的有差异。
两数之和
因为需要输出位置，所以将原数组变成一个元组数组再排序。
排完序后数组具有单调性，前后两个指针的和与 \(x\) 比大小，小就 l ++ 大就 r -- 。
具体代码为
import sys
from math import inf
if 1:
inp = lambda: sys.stdin.readline().strip()
II = lambda: int(inp())
MII = lambda: map(int, inp().split())
LII = lambda: list(MII())
Max = lambda x, y: x if x > y else y
Min = lambda x, y: x if x < y else y
def main():
n, k = MII()
a = LII()
a = [(x, i+1) for i, x in enumerate(a)]
a.sort()
l, r = 0, n - 1
while l < r:
s = a[l][0] + a[r][0]
if s > k:
r -= 1
elif s < k:
l += 1
else:
print(a[l][1], a[r][1])
return
print("IMPOSSIBLE")
if __name__ == "__main__":
main()
还有更有学习意义的算法，即使用哈希表边枚举边查询。这个技巧很有用，很多场景用到的有很大的启发意义。
# 模版代码直接复制即可
def main():
n, k = MII()
a = LII()
mp = {}
for i, x in enumerate(a):
if k - x in mp: # 查是否遍历过
print(mp[k - x], i + 1)
return
mp[x] = i + 1 # 记录出遍历的部分
print("IMPOSSIBLE")
三数之和
在两数之和的外面套一层 for 循环转化求剩余区间的两数之和。
具体代码为
# 模版代码直接复制即可
def main():
n, k = MII()
a = LII()
a = [(x, i+1) for i, x in enumerate(a)]
a.sort()
for i in range(n):
l, r = i + 1, n - 1
while l < r:
s = a[l][0] + a[r][0] + a[i][0]
if s > k:
r -= 1
elif s < k:
l += 1
else:
print(a[i][1], a[l][1], a[r][1])
return
print("IMPOSSIBLE")
四数之和
按照三数之和的思路套两层 for 循环时会超时，这时考虑剪枝和哈希表。
直觉告诉我们可以预先估计数的大小然后及时止损。
比如 2, 3, 5, 8, 11 和 x = 8 ，当 \(a_i=3\) 的时候已经没有往后遍历的必要了，因为有序数组在 \(i\) 以后的元素都大于等于 \(a_i\) ，所以这里最小也是 \(9\) ，不可能由等于 \(8\) 的机会了。