和為s的連續(xù)正數(shù)序列

題目描述

輸入一個正整數(shù) target 逻杖，輸出所有和為 target 的連續(xù)正整數(shù)序列（至少含有兩個數(shù)）匣椰。

序列內(nèi)的數(shù)字由小到大排列，不同序列按照首個數(shù)字從小到大排列朱监。

示例：

輸入：target = 9
輸出：[[2,3,4],[4,5]]

輸入：target = 15
輸出：[[1,2,3,4,5],[4,5,6],[7,8]]

提示：
1 <= target <= 10^5

轉載來源：力扣（LeetCode）

題目分析

一開始想這題是關于數(shù)組的求和饭豹，很有可能是和動態(tài)規(guī)劃有關，考點就是通過動態(tài)規(guī)劃來存放中間計算量毕贼，來達到加速效果温赔，不然會卡時間超限，嗯我真是天才鬼癣，一看題目什么都知道了陶贼；

動態(tài)規(guī)劃

然后就秒想出狀態(tài)轉移方程sum[i][j] = sum[i-1][j-1] + j，時空都是O(N^2)待秃，然后再天才的千方百計將空間復雜度下降到O(N)拜秧，并添加一些提前結束計算循環(huán)的剪枝,再按照題目要求輸出，才提交上去章郁，果然AC了枉氮！只不過...

Kotlin提交

Java提交

我真是個弟弟淹辞，然后我就重新想，這道題的第I部分是前后夾擊俘侠，但是這道題這樣做不行象缀，因為要求是連續(xù)和，不能前后計算爷速，因為連續(xù)和為target的幾個數(shù)（兩個以上）央星，最大的只能是target/2，所以就從target/2往前推惫东，一開始設置尾指針tail為target/2莉给，頭指針head為target/2-1，長度len為2廉沮，和sum為head+tail颓遏，就開始下面的循環(huán)

• sum為target，就將從head開始滞时，包裝出一個長度為len的步長為1的單增數(shù)組叁幢，并添加到答案，重點來了坪稽，因為從head到tail的和為target曼玩，那么，tail就肯定不能出現(xiàn)在長度len更長的其他答案里面（反證法窒百，如果在黍判，和就肯定比target大），tail就需要往前推篙梢，tail往前推了样悟，head+tail肯定就小于target了，所以head也往前推庭猩，sum就比原來小了len那么多

• sum比target大窟她，那tail肯定要排除在后面的答案序列里面，舉個例子蔼水，2+3+4比8要大震糖，我們是從后往前的，如果不把4踢掉趴腋，那么連續(xù)序列肯定比（2+3+4）要長吊说，肯定不符合答案论咏，所以這種情況下前后指針都往前推，sum就比原來小了len那么多

• sum比target小颁井，這種情況只能head往前推厅贪，不能head和tail都往前推，因為head to tail比target小雅宾，都往前推的話還是比target小养涮，沒意義，只能通過增長序列來求解眉抬，所以這種情況head往前推贯吓，sum+=head，len++

ArrayList<int[]> ans = new ArrayList<>();
        int tail = (target % 2 == 0) ? target / 2 : target / 2 + 1;
        int head = tail - 1;
        int len = 2;
        int sum = tail + head;
        while(head != 0){
            if(sum == target){
                int[] tmp = new int[len];
                for (int i = 0; i < tmp.length; i++) {
                    tmp[i] = head + i;
                }
                ans.add(tmp);
                tail--;
                head--;
                sum -= len;
            }else if(sum > target){
                head--;
                tail--;
                sum -= 2;
            }else{
                head--;
                len++;
                sum += head;
            }
        }
        int[][] ret = new int[ans.size()][];
        for (int i = 0; i < ans.size(); i++) {
            ret[i] = ans.get(ans.size() - i - 1);
        }
        return ret;

代碼文件蜀变，kotlin的為DP算法悄谐，Java為指針算法