給定長度為n的整數數列：a0,a1,..,an-1，以及整數S。這個數列會有連續的子序列的整數總和大于S的，求這些數列中，最小的長度。

又見排序分析

原題

給定大小為n的數組A，A中的元素有正有負。請給出方法，對其排序，保證：


• 負數在前面，正數在后面
• 正數之間相對位置不變
• 負數之間相對位置不變

能夠做到時間復雜度為O(n)，空間復雜度為O(1)么？

分析

這類題目，還有其他的變形，比如，數組A有奇數和偶數，排序奇數在前偶數在后，并且奇數和偶數內部的相對順序不能變。那么這類的題目，該如何解決呢？

首先，暴力法可行：從左到右掃描數組，遇到***個負數，與其前面的每一個元素進行交換，直到***個位置，這里并不能直接交換， 因為這樣就改變了正數的相對位置了。后面的繼續掃描，第二個負數，依次交換到第二個位置。依次類推。算法總的時間復雜度為O(n^2)。

上面這個方法，大多數同學，都可以給出。那么，是否有更快的方法呢？大家請看下面的方法：統計負數的個數，設為M

• 找到索引k>M的***個負數
• 使用i和j兩個索引，i從0開始，直到遇到***個正數，j從k開始，直到遇到***個負數。交換i，j位置上的數，然后符號取反
• 對于A[0,M]和A[M, n]分別執行上面三步
• 修正符號：前面的M個為負數，后面的為正數。

下面舉例來說明，對于數組{-1,1,3,-2,2}，根據描述，有M=2，k=3。i遇到***個正數為A1=1，j 遇到***個負數為A[3]=-2。然后交換i和j位置上的值， 數組變為{-1, -2, 3, 1, 2}, 然后改變符號，得到{-1,2,3,-1,2}。然后遞歸處理{-1,2},{3,-1,2}，最終得到{-1,2,1,-3,2}。進行***一步，修正 符號, 得到{-1,-2,1,3,2}。即為最終答案。這個方法是nlog(n)的，比上面的提高了一些。

但是上面的方法，仍舊不是O(n)的。那么O(n)的方法，是否存在呢？我們認為，接近O(n)的方法是有的。但是，方法過于復雜。這類問題，可以統稱為 stable 0-1 sorting。還是蠻有意思的。大家感興趣的話，可以參考下面的文章：http://www.diku.dk/hjemmesider/ansatte/jyrki/Paper/KP92b.pdf

原文鏈接：http://www.ituring.com.cn/article/56013