題目描述
小明很喜歡數(shù)學(xué),有一天他在做數(shù)學(xué)作業(yè)時,要求計算出9~16的和,他馬上就寫出了正確答案是100。但是他并不滿足于此,他在想究竟有多少種連續(xù)的正數(shù)序列的和為100(至少包括兩個數(shù))。沒多久,他就得到另一組連續(xù)正數(shù)和為100的序列:18,19,20,21,22?，F(xiàn)在把問題交給你,你能不能也很快的找出所有和為S的連續(xù)正數(shù)序列? Good Luck!
輸出描述:
輸出所有和為S的連續(xù)正數(shù)序列。序列內(nèi)按照從小至大的順序，序列間按照開始數(shù)字從小到大的順序
看見題目之后還是本能的想到用笨笨的方法去實現(xiàn)，即分別從n為奇數(shù)和偶數(shù)的角度去考慮，這樣的思路比較清晰，記錄一下（這里摘自Java版答案中的分析，我覺得語言組織得比我自己的好多了，故摘抄一下）：
鏈接：https://www.nowcoder.com/questionTerminal/c451a3fd84b64cb19485dad758a55ebe
來源：牛客網(wǎng)
1）由于我們要找的是和為S的連續(xù)正數(shù)序列，因此這個序列是個公差為1的等差數(shù)列，而這個序列的中間值代表了平均值的大小。假設(shè)序列長度為n，那么這個序列的中間值可以通過（S / n）得到，知道序列的中間值和長度，也就不難求出這段序列了。
? 2）滿足條件的n分兩種情況：
n為奇數(shù)時，序列中間的數(shù)正好是序列的平均值，所以條件為：(n & 1) == 1 && sum % n == 0；
n為偶數(shù)時，序列中間兩個數(shù)的平均值是序列的平均值，而這個平均值的小數(shù)部分為0.5，所以條件為：(sum % n) * 2 == n.
? 3）由題可知n >= 2，那么n的最大值是多少呢？我們完全可以將n從2到S全部遍歷一次，但是大部分遍歷是不必要的。為了讓n盡可能大，我們讓序列從1開始，
圖中代碼不夠簡潔，重復(fù)率高，只是為了展示清晰。上述代碼在pycharm中自行調(diào)試時ok的，但是在牛客中提交結(jié)果是算法復(fù)雜度太大，或是超出內(nèi)存限制，所以只能求助于答案中國中的神解答了（唉笨），以下記錄一下：
設(shè)定兩個指針，先分別指向數(shù)字1和數(shù)字2，并設(shè)這兩個指針為small和big，對small和big求和，如果和大于目標值，則從當前和中刪除small值，并把small值加一，如果和小于目標值，則把big值加一，再把新的big值加入和中。如果和等于目標值，就輸出small到big的序列，同時把big加一并加入和中，繼續(xù)之前的操作。（看答案都看半天才看懂，打死我也想不出這樣的答案啊TT）
也就是通過兩個指針遍歷了半個數(shù)組的全部組合可能
