題目描述
小明很喜歡數學,有一天他在做數學作業時,要求計算出9~16的和,他馬上就寫出了正確答案是100。但是他并不滿足于此,他在想究竟有多少種連續的正數序列的和為100(至少包括兩個數)。沒多久,他就得到另一組連續正數和為100的序列:18,19,20,21,22。現在把問題交給你,你能不能也很快的找出所有和為S的連續正數序列? Good Luck!
輸出描述:
輸出所有和為S的連續正數序列。序列內按照從小至大的順序，序列間按照開始數字從小到大的順序
算法描述：對于一個連續正數數組，求和為S的連續正數序列，那么我們的連續數組只可能發生在1到sum之間，所以我們將最初的輔助變量small設為1， big設為sum， 當我們檢查small到big之間的和大于sum的時候，我們將big減小，當和小于sum的時候，我們就增大big 和small， 當相同的時候，就打印數組，并增大small。直到small >= big的時候，也就代表序列不可能存在，所以就代表掃描結束。
代碼如下：
public static ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) { ArrayList<ArrayList<Integer>> result = new ArrayList<>(); if(sum <= 0){ return result; } int small = 1; int big = sum; int mid = (1 + sum) / 2; while (small < big){ float check = (((small + big) * (big - small + 1)) / 2.0f); if (check == sum){ ArrayList<Integer> temp = new ArrayList<>(); for (int i = small; i <= big; i++) { temp.add(i); } result.add(temp); small ++; }else if (check < sum){ small ++; big ++; }else{ big --; } } return result; }新聞熱點
疑難解答
