##題目描述 小明很喜歡數學,有一天他在做數學作業時,要求計算出9~16的和,他馬上就寫出了正確答案是100，但是他并不滿足于此,他在想究竟有多少種連續的正數序列的和為100(至少包括兩個數)，沒多久,他就得到另一組連續正數和為100的序列:18,19,20,21,22，現在把問題交給你,你能不能也很快的找出所有和為S的連續正數序列? Good Luck!
輸出描述:
輸出所有和為S的連續正數序列，序列內按照從小至大的順序，序列間按照開始數字從小到大的順序，
思路
題目意思是求一組公差為1和為sum的等引數列，
-
方法1（推薦）：
快慢指標滑動視窗，
設定兩個指標指向等引數列左右兩端，利用等引數列求和公式驗證，
右指標右移一步，相當于拿一個未使用的最小值進來，
左指標左移一步，相當于拿一個已使用的最小值出去，
時間復雜度O(n)，空間復雜度O(1)， -
方法2:
等引數列求和，
在本題場景中，符合條件的等引數列的長度上限，是從1開始的數列的長度，
可能符合條件的最長的等引數列和為n(n+1)/2，此時，d = 1， a1 = 1，
根據不等式 Sn = n(n+1)/2，可以求解出 n <= √（2Sn），
得到數列長度n的取值范圍后，可以直接使用Sn除以n得到數列的平均數，從而求出數列，
當n為奇數時，求得的正好是等引數列中間的值，
當n為偶數時，求得的是均值，該均值小數部分是0.5，即Sn%n=n/2 => Sn%n*2=n，
時間復雜度O(√n)，空間復雜度O(1)，
滑動視窗代碼（演算法思維容易接受）
import java.util.ArrayList;
public class Solution {
public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
if(sum < 3) return list;
int low = 1;
int high = 2;
int curr = 3;
// 判斷條件不能包含等于，至少需要包含兩個數字，所以low最大只能到high-1，
while(low < high) {
curr = (low + high) * (high - low + 1)/2;
if(curr == sum) {
ArrayList<Integer> item = new ArrayList<Integer>();
for(int i = low; i <= high; i++) {
item.add(i);
}
list.add(item);
high++;
} else if(curr < sum) {
high++;
} else {
low++;
}
}
return list;
}
}
數學方法代碼（需要分析推導）
import java.util.ArrayList;
public class Solution {
public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
if(sum < 3) return list;
for(int len = (int)Math.sqrt(2*sum); len > 1; len--) {
if((len&1) == 1 && sum % len == 0 || sum % len * 2 == len) {
int k = sum / len - (len - 1) / 2;;
ArrayList<Integer> item = new ArrayList<Integer>();
for(int i = 0; i < len; i++) {
item.add(k++);
}
list.add(item);
}
}
return list;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/83491.html
標籤：其他
上一篇：陣列中只出現一次的數字
下一篇：和為S的兩個數字