时间戳

首页 > 解决方案 > 在未排序的数字数组中查找具有给定总和的所有对

list - 在未排序的数字数组中查找具有给定总和的所有对

问题描述

例如，该函数将有两个输入：

输出将是与目标相加的所有数字对的数组，例如[(1,9),(8,2),(5,5),(7,3),(6,4)]。

我完全不知道如何创建此代码。如果有人可以提供一些见解，以下是我到目前为止所拥有的，但它不起作用：

sums :: (Num a, Num b) => [a] -> b -> [(a,a)]
sums ([x] i) = (x i)
sums (x:xs) i
    | x == [] = []
    | x + sums(xs) == i = [(x,xs)]
    | otherwise = []

标签： listhaskellrecursionsumcombinations

解决方案

您的尝试在句法和语义上都有很多问题。这是一种可能的解决方案。它不是递归的，但我希望它能帮助您理解问题（请参阅最后关于递归的建议）：

sums :: (Num a, Eq a) => [a] -> a -> [(a,a)]
sums l s = filter (\(x,y) -> x+y == s) [ (x,y) | x <- l, y <- l ]
  • [ (x,y) | x <- l, y <- l ]定义一个包含所有可能对的列表
  • \(x,y) -> x+y == s是一个函数，给定一对告诉它是否满足你的条件
  • filter使用该函数过滤所有可能对的列表

请花点时间了解一些主题：

  • 如何编写函数签名
  • 列表和它们最常用的功能（例如filter）
  • 理解语法 ( [ (x,y) | x <- l, y <- l ])
  • Lambda 表达式 ( \(x,y) -> x+y == s)
  • 懒惰的评价。您尝试在一个函数中完成所有操作：遍历列表、配对、检查它们是否满足条件。上面的解决方案首先定义了所有可能的组合，然后过滤，只选择那些总和为 的组合s。如果您来自命令式编程，从概念上讲更简单，也很有效，直观地思考它可能看起来很慢。

正如评论中所指出的，表达这一点的最紧凑的方式是使用理解将条件“即时”应用于生成的组合的能力：

sums l s = [ (x,y) | x <- l, y <- l, x+y == s ]

但是，尝试使用递归解决问题对您更有指导意义。

建议：保留结构filter (\(x,y) -> x+y == s) (all_pairs l)，但尝试自己想出一个递归函数all_pairs，从列表中生成所有可能的对，而不是像我那样使用理解语法。您需要编写的函数比您之前尝试过的函数要简单得多。只需从列表中制作所有对，没有条件，没有检查。

推荐阅读