題目描述
小明很喜歡數(shù)學(xué),有一天他在做數(shù)學(xué)作業(yè)時(shí),要求計(jì)算出9~16的和,他馬上就寫出了正確答案是100东臀。但是他并不滿足于此,他在想究竟有多少種連續(xù)的正數(shù)序列的和為100(至少包括兩個(gè)數(shù))恢总。沒多久,他就得到另一組連續(xù)正數(shù)和為100的序列:18,19,20,21,22。現(xiàn)在把問題交給你,你能不能也很快的找出所有和為S的連續(xù)正數(shù)序列? Good Luck!
輸出描述:
輸出所有和為S的連續(xù)正數(shù)序列谢澈。序列內(nèi)按照從小至大的順序拨扶，序列間按照開始數(shù)字從小到大的順序
看見題目之后還是本能的想到用笨笨的方法去實(shí)現(xiàn)逗余，即分別從n為奇數(shù)和偶數(shù)的角度去考慮，這樣的思路比較清晰影钉，記錄一下（這里摘自Java版答案中的分析画髓，我覺得語言組織得比我自己的好多了，故摘抄一下）：
鏈接：https://www.nowcoder.com/questionTerminal/c451a3fd84b64cb19485dad758a55ebe
來源：牌轿客網(wǎng)
1）由于我們要找的是和為S的連續(xù)正數(shù)序列奈虾，因此這個(gè)序列是個(gè)公差為1的等差數(shù)列，而這個(gè)序列的中間值代表了平均值的大小廉赔。假設(shè)序列長(zhǎng)度為n肉微，那么這個(gè)序列的中間值可以通過（S / n）得到，知道序列的中間值和長(zhǎng)度昂勉，也就不難求出這段序列了浪册。
? 2）滿足條件的n分兩種情況：
n為奇數(shù)時(shí)，序列中間的數(shù)正好是序列的平均值岗照，所以條件為：(n & 1) == 1 && sum % n == 0村象；
n為偶數(shù)時(shí)笆环，序列中間兩個(gè)數(shù)的平均值是序列的平均值，而這個(gè)平均值的小數(shù)部分為0.5厚者，所以條件為：(sum % n) * 2 == n.
? 3）由題可知n >= 2躁劣，那么n的最大值是多少呢？我們完全可以將n從2到S全部遍歷一次库菲，但是大部分遍歷是不必要的账忘。為了讓n盡可能大，我們讓序列從1開始熙宇，
圖中代碼不夠簡(jiǎn)潔鳖擒，重復(fù)率高，只是為了展示清晰烫止。上述代碼在pycharm中自行調(diào)試時(shí)ok的蒋荚，但是在牛客中提交結(jié)果是算法復(fù)雜度太大馆蠕，或是超出內(nèi)存限制期升，所以只能求助于答案中國(guó)中的神解答了（唉笨），以下記錄一下：
設(shè)定兩個(gè)指針互躬，先分別指向數(shù)字1和數(shù)字2播赁，并設(shè)這兩個(gè)指針為small和big，對(duì)small和big求和吼渡，如果和大于目標(biāo)值容为，則從當(dāng)前和中刪除small值，并把small值加一诞吱，如果和小于目標(biāo)值舟奠，則把big值加一竭缝，再把新的big值加入和中房维。如果和等于目標(biāo)值，就輸出small到big的序列抬纸，同時(shí)把big加一并加入和中咙俩，繼續(xù)之前的操作。（看答案都看半天才看懂湿故，打死我也想不出這樣的答案啊TT）
也就是通過兩個(gè)指針遍歷了半個(gè)數(shù)組的全部組合可能
