haskell中的两个指针方法
如何在haskell中实现两个指针方法？
例如，在子数组和问题中，我们想要找到一个和为x的子数组。
示例: 1，3, 5，18查找和为8的子数组。答案: 3，5
在命令式编程中，两个指针方法通过维护指向子数组的第一个和最后一个值的指针来给出解决方案。并且当得到的子数组和是lteq到x时，右指针移动。
我想出的最接近的想法是通过scanl和takeWhile的组合，但我无法想象如何在我们扫描解决方案时滑动“蠕虫”。
我对algo的简单实现描述
go' :: (Ord a, Num a) => a -> [a] -> Bool
go' x l
| null l = False
| x `elem` takeWhile (<=x) (scanl' (+) 0 l) = True
| otherwise = go' x (tail l)回答 3
Stack Overflow用户
发布于 2021-06-13 20:22:20
你总能做的一件事就是把命令式代码直接翻译成Haskell：
import qualified Data.Vector as V
twoPointers :: Int -> [Int] -> Maybe [Int]
twoPointers x xs = go 0 0 0 where
arr = V.fromList xs
n = V.length arr
go s l r
| r == n = Nothing
| s' == x = Just (V.toList (V.slice l (r + 1 - l) arr))
| s' <= x = go s' l (r + 1)
| otherwise = go (s - arr V.! l) (l + 1) r
where
s' = s + arr V.! r编辑:下面的函数解还不是O(n)，对不起。
对于功能更强大的解决方案，我将按如下方式进行推导。您已经推荐了scanl和takeWhile，我将把它与tails结合起来，以获得每个子序列的所有和的列表：
ghci> map (takeWhile (<= 5) . scanl (+) 0) (tails [1,2,3])
[[0,1,3],[0,2,5],[0,3],[0]](请注意，您可以使用一元绑定来编写它：takeWHile (<= 5) . scanl (+) 0 =<< tails [1,2,3]，我认为这样看起来更好)
有了这个，我们可以很容易地解决决策问题版本，我们只想确定是否存在具有特定和的子序列：
subseqSumDecision :: Int -> [Int] -> Bool
subseqSumDecision x xs = x `elem` concatMap (takeWhile (<= x) . scanl (+) 0) (tails xs)要获得实际的子序列，我认为最简单的方法是更改scanl的参数，使其也构建子序列：
ghci> concatMap (takeWhile ((<= 5) . fst) . scanl (\(s, xs) x -> (s + x, x : xs)) (0, [])) (tails [1,2,3])
[(0,[]),(1,[1]),(3,[2,1]),(0,[]),(2,[2]),(5,[3,2]),(0,[]),(3,[3]),(0,[])]现在我们可以简单地使用lookup函数来查找子序列：
subseqSumReversed :: Int -> [Int] -> Maybe [Int]
subseqSumReversed x xs = lookup x
$ concatMap
(takeWhile ((<= x) . fst) . scanl (\(s, xs) x -> (s + x, x : xs))
(0, []))
$ tails xs您可能会注意到，这将返回颠倒的子序列，因此您只需在末尾再次颠倒它：
subseqSum :: Int -> [Int] -> Maybe [Int]
subseqSum x xs = fmap reverse
$ lookup x
$ concatMap
(takeWhile ((<= x) . fst) . scanl (\(s, xs) x -> (s + x, x : xs))
(0, []))
$ tails xsStack Overflow用户
发布于 2021-06-14 01:36:20
这里有一个相对简单的方法来解决这个问题：
getSubarrayIndices :: Int -> [Int] -> Maybe (Int, Int)
getSubarrayIndices target list =
let prefixSumsWithIndices = zip [0..] $ scanl' (+) 0 list
loop begin@((beginIdx, beginSum):restBegin) end@((endIdx, endSum):restEnd) =
case compare (endSum - beginSum) target of
LT -> loop begin restEnd
EQ -> Just (beginIdx, endIdx)
GT -> loop restBegin end
loop _ _ = Nothing
in loop prefixSumsWithIndices prefixSumsWithIndices如果为getSubarrayIndices target list = Just (beginIdx, endIdx)，则为target = sum (drop beginIdx (take endIdx list))。如果为getSubarrayIndices target list = Nothing，则不存在list求和到target的相邻子序列。
值得注意的是，人们应该很少使用列表作为存储数据的方法。如果您正在寻找高性能，Haskell中的列表真的应该被视为命令式语言中的控制流机制的替代品，而不是一种存储将被多次循环的数据的手段。在这种情况下，使用列表和使用数组的渐近时间复杂度是相等的，但恒定因子将有利于使用数组。在这种情况下，我们实际上可以通过创建两个prefixSumsWithIndices副本来提高算法的内存复杂度，如下所示：
getSubarrayIndices :: Int -> [Int] -> Maybe (Int, Int)
getSubarrayIndices target list =
let prefixSumsWithIndices () = zip [0..] $ scanl' (+) 0 list
loop begin@((beginIdx, beginSum):restBegin) end@((endIdx, endSum):restEnd) =
case compare (endSum - beginSum) target of
LT -> loop begin restEnd
EQ -> Just (beginIdx, endIdx)
GT -> loop restBegin end
loop _ _ = Nothing
in loop (prefixSumsWithIndices ()) (prefixSumsWithIndices ())这是因为在原始算法中，当end先于begin时，所有中间前缀和都存储在内存中的某个地方。在算法的第二个版本中，它创建了两个列表，两个列表都将在消费时生成，因此在begin重新计算中间前缀和时，没有中间前缀和要存储。因此，我们的新代码使用O(1)辅助内存。
Stack Overflow用户
发布于 2021-06-14 07:21:15
既然你提到了一个双指针方法，我们实际上可以使用一个。我们将保留一个指向子序列的第一个元素的指针，以及一个指向最后一个元素的指针。我们还将跟踪子序列的大小及其总和。
import Numeric.Natural
getSubarray :: Natural -> [Natural] -> Maybe [Natural]
getSubarray goal = \xs -> go 0 0 xs xs
where
go sz total start []
| total == goal
-- These shenanigans avoid leaking the remainer
-- of the list.
, (taken, !_) <- splitAt sz start
= Just taken
| otherwise = Nothing
go sz total ~start@(a:as) end@(x : xs) = case compare total goal of
EQ
| (taken, !_) <- splitAt sz start
-> Just taken
LT -> go (sz + 1) (total + x) start xs
GT -> go (sz - 1) (total - a) as endhttps://stackoverflow.com/questions/67958065
复制相似问题
腾讯云开发者
