匹配值对字符串的总和 [英] Matching the sum of values on string

问题描述

我有一个空格分隔数值的字符串：

  70 58 81 909 70 215 70 1022 580 930 898 70 276 31 11 ** 920 ** 898 1503 195 770 573 508 1015 31 8 815 1478 31 1022 31 1506 31 ** 318 500 358 865 ** 358 991 518 58 450 420 487 31 1478 108 70 1022 31 215 318 500 61 31 655 1061 918 54 898 31 8 1011 9 8 459 346 770 751 31 346 770 880 1171 688 1680 31 1002 769 500 61 8 702 898 8 1206 31 709 565 8 138 58 215 81 1171 31 288 500 380 70 284 1500 565 31 601 55 1501 490 565 530 56 990 380 1061 770 345 1171 31 55 1100 605 1471 1234 ** 31 470 725 358 114 56 9 55 ** 1100 1610 1471 1000 971 565 55 1100 1610 1061 770 345 949 31 370 52 688 1680 770 880 1171 163 249 151 489 653 56 990 380 503 490 770 1376 1056 31 8 64 490 565 55 108 56 1178 501 653 898 860 565 31 315 61 509 108 501 653 31 349 249 151 489 246 56 990 380 1070 573 1663 725 821 31 70 373 1171 490 565 55 108 ...
 

我想要得到的字符串，其中数字组合总和为x的所有出现。所以，如果我搜索：2041应该返回数组（318 500 358 865），或者如果我搜索：1818应该返回数组（920 898，31 470 725 358 114 56 9 55）<。 / P>

我还需要的解决方案是最佳的，因为数字的字符串可以总结到几十万。

原则的理论来解释将是一件好事，但preferred语言是PHP或NodeJs如果解决方案是由编程语言给出。即使是MySQL的解决方案将是很好，如果可能的话。但是，任何一种语言的解决方案将是很好的反正。

附加说明

• 数字都是正整数
• 数值是1-10000之间

解决方案

在这里你去，在Python。这具有线性复杂度：

 高清list2string（ALIST）：
    返回。加入（图（STR，ALIST））

高清string2list（S）：
    返回目录（地图（INT，s.split（）））

高清find_number（一，计）：
    U = 0
    y = 0的＃该间隔的当前总和（U .. v）的
    RES = []
    为V IN范围（0，LEN（一））：
        ＃在该点的时间间隔总和y是比所需的总小，
        ＃所以我们将区间的右端前进
        Y + = A [V]
        而在Y＆GT; =总：
            如果y ==总：
                res.append（list2string（A [U：V + 1]））
            ＃如果当前总和过大，移动间隔的左端向前
            Ÿ -  =一[U]
            U + = 1
    回报水库



文=70 58 81 909 70 215 70 1022 580 930 898
ALIST = string2list（文本）
打印（find_number（ALIST，285））
 

我假设有在你的列表中没有负值，并且该列表完全由用空格分隔的整数。你不应该将其翻译成其它语言的任何问题。我希望算法是不言自明，如果不问。

I have a string of numerical values separated with spaces:

70 58 81 909 70 215 70 1022 580 930 898 70 276 31 11 **920 898** 1503 195 770 573 508 1015 31 8 815 1478 31 1022 31 1506 31 **318 500 358 865** 358 991 518 58 450 420 487 31 1478 108 70 1022 31 215 318 500 61 31 655 1061 918 54 898 31 8 1011 9 8 459 346 770 751 31 346 770 880 1171 688 1680 31 1002 769 500 61 8 702 898 8 1206 31 709 565 8 138 58 215 81 1171 31 288 500 380 70 284 1500 565 31 601 55 1501 490 565 530 56 990 380 1061 770 345 1171 31 55 1100 605 1471 1234 **31 470 725 358 114 56 9 55** 1100 1610 1471 1000 971 565 55 1100 1610 1061 770 345 949 31 370 52 688 1680 770 880 1171 163 249 151 489 653 56 990 380 503 490 770 1376 1056 31 8 64 490 565 55 108 56 1178 501 653 898 860 565 31 315 61 509 108 501 653 31 349 249 151 489 246 56 990 380 1070 573 1663 725 821 31 70 373 1171 490 565 55 108...

I want to get all occurrences of the string, where combined sum of numbers is x. So, if I search: 2041 it should return an array ("318 500 358 865") or if I search: 1818 it should return an array ("920 898", "31 470 725 358 114 56 9 55").

I also need solution to be optimal, because string of numbers can sum up to hundreds of thousands.

Principle explained in theory would be good, but preferred languages are PHP or NodeJs if solution is given by programming language. Even MySQL solution would be nice, if possible. But solution by any language would be nice anyway.

Extra notes

• numbers are all positive integers
• number values are between 1-10000

解决方案

Here you go, in Python. This has linear complexity:

def list2string( alist ):
    return " ".join( map(str, alist ))

def string2list( s ):
    return list(map( int, s.split() ))

def find_number( a, total ):
    u = 0
    y = 0 # the current sum of the interval (u .. v)
    res = []
    for v in range( 0, len(a) ):
        # at this point the interval sum y is smaller than the requested total,
        # so we move the right end of the interval forward
        y += a[v]
        while y >= total:
            if y == total:
                res.append( list2string( a[ u : v+1 ] ) )
            # if the current sum is too large, move the left end of the interval forward
            y -= a[u]
            u += 1
    return res



text = "70 58 81 909 70 215 70 1022 580 930 898"
alist = string2list(text)
print( find_number( alist, 285) )

I'm assuming there are no negative values in your list, and the list consists purely of integers separated by spaces. You shouldn't have any problems translating it into any other language. I hope the algorithm is self-explanatory, if not ask.

这篇关于匹配值对字符串的总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！