JZ74 和為S的連續正數序列
題目
小明很喜歡數學,有一天他在做數學作業時,要求計算出9~16的和,他馬上就寫出了正確答案是100，
但是他并不滿足于此,他在想究竟有多少種連續的正數序列的和為100(至少包括兩個數)，
沒多久,他就得到另一組連續正數和為100的序列:18,19,20,21,22，
現在把問題交給你,你能不能也很快的找出所有和為S的連續正數序列?
方法1 列舉法
思路
演算法實作
從數字1開始列舉連續的數字，將其累加判斷其是否等于目標，
如果小于目標數則繼續往后累加，
如果大于目標數說明會超過，跳出，
繼續列舉下一個數字開始的情況（比如2，比如3），
這樣每次都取連續的序列，只有剛好累加和等于目標數才可以記錄從開始到結束這一串數字，代表是一個符合的序列，
具體做法：
step 1：從1到目標值一半向下取整作為列舉的左區間，即每次序列開始的位置，
step 2：從每個區間首部開始，依次往后累加，如果大于目標值說明這一串序列找不到，換下一個起點，
step 3：如果加到某個數字剛好等于目標值，則記錄從區間首到區間尾的數字，
代碼
package mid.JZ74和為S的連續正數序列;
import java.util.ArrayList;
public class Solution {
/**
* 列舉法
* @param sum
* @return
*/
public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
if (sum == 0) return new ArrayList<>();
//因為序列至少兩個數，因此列舉最多到該數字的一半向下取整
int sum1 = 0;
int mid = (sum - 1) / 2;
for (int i = 1; i <= mid; i++) {
for (int j = i; ; j++) {
sum1 += j;
if (sum1 > sum) {
sum1 = 0;
break;
} else if (sum1 == sum) {
ArrayList<Integer> temp = new ArrayList<>();
for (int k = i; k <= j; k++)
temp.add(k);
res.add(temp);
sum1 = 0;
break;
}
}
}
return res;
}
}
方法2 滑動視窗（推薦使用）
思路
演算法實作
從某一個數字開始的連續序列和等于目標數如果有，只能有一個，于是我們可以用這個性質來使區間滑動，
兩個指標l、r指向區間首和區間尾，公式(l+r)?(r?l+1)/2計算區間內部的序列和，
如果這個和剛好等于目標數，說明以該區間首開始的序列找到了，記錄下區間內的序列，同時以左邊開始的起點就沒有序列了，于是左區間收縮；
如果區間和大于目標數，說明該區間過長需要收縮，只能收縮左邊；
如果該區間和小于目標數，說明該區間過短需要擴大，只能向右擴大，移動區間尾，
具體做法：
step 1：從區間[1,2][1,2][1,2]開始找連續子序列，
step 2：每次用公式計算區間內的和，若是等于目標數，則記錄下該區間的所有數字，為一種序列，同時左區間指標向右，
step 3：若是區間內的序列和小于目標數，只能右區間擴展，若是區間內的序列和大于目標數，只能左區間收縮，
代碼
package mid.JZ74和為S的連續正數序列;
import java.util.ArrayList;
public class Solution {
/**
* 滑動視窗（推薦使用）
* @param sum
* @return
*/
public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
for (int l = 1, r = 2; l < r; ) {
int sum1 = (l + r) * (r - l + 1) / 2;
if (sum1 == sum) {
ArrayList<Integer> temp = new ArrayList<>();
for (int i = l; i <= r; i++) {
temp.add(i);
}
res.add(temp);
l++;
} else if(sum1 < sum) {
r++;
} else {
l++;
}
}
return res;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/540979.html
標籤：其他