这是地道的哈斯克尔二和问题吗

Question

给定整数列表和目标和，确定是否存在是一对不同的数字，其总和为目标总和。

这是一个经典的LeetCode问题，我写的解决方案包括

1. 创建一个辅助的HashMap，它可以让我们确定是否在以前的迭代中看到了给定的数字
2. 遍历每个数字：
   1. 检查target_sum - current_number是否在HashMap中，如果返回True
   2. 否则，将current_number添加到哈希映射中

O(n(时间|O(n(空间

我挑战自己用Haskell写这篇文章，并成功了，但不确定这是否是惯用代码。请告诉我。

import Data.Map (Map)
import qualified Data.Map as Map
twoSum :: [Int] -> Int -> Bool
twoSum xs target_sum =
let seen = Map.empty
in twoSum' xs target_sum seen
twoSum' :: [Int] -> Int -> Map Int Int -> Bool
twoSum' [] target_sum seen = False
twoSum' (x:xs) target_sum seen
| Map.lookup (target_sum - x) seen  /= Nothing = True
| otherwise                                    = let new_seen = Map.insert x 0 seen
in twoSum' xs target_sum new_seen

Answer 1

严格来说，该算法的时间是O(n log n(，因为insert是在O(log n(中完成的。

在这里使用Map有点奇怪。您在这里基本上想要做的是使用Set，因为您在这里与键关联的值实际上并不重要。这也删除了有点"丑陋"的Map.lookup ... /= Nothing：例如，Integer确实是Eq类型类的实例，但不是类型是Eq类型类的成员，因此，如果某个东西不是Nothing，则使用(/=)进行检查，要求Maybe中封装的类型成为Eq类型类的一员。

我认为你可以先用fromList构造一组值，然后检查是否有x的值target - x与x不同，并且是Set:的一部分

import qualified Data.Set as S
twoSum :: [Int] -> Int -> Bool
twoSum xs target = any (x -> target - x /= x &&S.member (target - x) mySet) xs
where mySet =S.fromList xs