我有一個數組,其中包含按排序順序排列的數字。 我給了一個數字,並要求將它表示爲數組中連續數字的總和。我怎麼做?如何將數字表示爲數組中連續數字的總和
例如,考慮一個數組
arr={2,3,5,7,11,13,17,19,23,29,31,37,41}
和一個數字,說41. 可以表示爲下面的
2+3+5+7+11+13
在多個15的情況下,它應該被表達作爲
3+5+7
我需要一個算法/代碼來有效地找到所有這些值。
我有一個數組,其中包含按排序順序排列的數字。 我給了一個數字,並要求將它表示爲數組中連續數字的總和。我怎麼做?如何將數字表示爲數組中連續數字的總和
例如,考慮一個數組
arr={2,3,5,7,11,13,17,19,23,29,31,37,41}
和一個數字,說41. 可以表示爲下面的
2+3+5+7+11+13
在多個15的情況下,它應該被表達作爲
3+5+7
我需要一個算法/代碼來有效地找到所有這些值。
讓x
是我們尋找的總和人數爲:
arr={2,3,5,7,11,13,17,19,23,29,31,37,41}
l=0 // index from where to start sum up (l left)
r=0 // index until where to sum up (r right)
label:
sum=arr[l]+...arr[r]
if(sum==x)
return (l,r);
if(sum<x)
r++
if(sum>x)
l++
goto label
您需要添加一些條件,以處理案件時,它是不可能找到的總和。
Visually explained example: x=36
{2,3,5,7,11,13,17,19,23,29,31,37,41}
() sum = 2 l=0 r=0
( ) sum = 5 l=0 r=1
( ) sum = 10 l=0 r=2
( ) sum = 17 l=0 r=3
( ) sum = 28 l=0 r=4
( ) sum = 41 l=0 r=5
( ) sum = 39 l=1 r=5
( ) sum = 36 l=2 r=5 -> return (2,5)
Result arr[2]+...+arr[5] = 36
我認爲你需要添加一個條件來打破如果(l> r)break的連續數字不能用6來表示的數字; – AnotherGeek
@AnotherGeek:這就是我說的這句話的意思:'你需要添加一些條件來處理無法找到總和的情況。' – MrSmith42
你是指「所有這些值」是什麼意思?你的意思是你想要所有的解決方案,如果有多種可能的方式來獲得給定的數字? – MrSmith42
這是一個提示:它可以在'O(n)'中完成。向我們展示您的代碼或解釋您吸吮的位置。 – MrSmith42
我試過在數組中找到兩個連續元素的總和並將其存儲在另一個數組中。這樣,我就可以找出所有表示爲兩個連續數字之和的數字。在這種情況下,如果不知道連續數字的數量,那麼很難表示數字,例如在41的情況下。 –