使用等差数列的结论
和为S的连续正数序列
http://www.nowcoder.com/questionTerminal/c451a3fd84b64cb19485dad758a55ebe
import java.util.ArrayList;
import java.util.Collections;
public class Solution {
int sum;
public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
this.sum = sum;
ArrayList<ArrayList<Integer>> ans = new ArrayList();
//等差数列： N*(A中) = sum, 关键是求 (A中)，求中间那个数
if(sum<=1)
{
return ans;
}
for(int i=1;i<sum;++i)
{
int mid = sum/i;
if((i&1)==1)
{
ArrayList p = getOdd(mid,false);
if(!p.isEmpty()) ans.add(p);
}else{
ArrayList p = getOdd(mid,true);
if(!p.isEmpty()) ans.add(p);
}
}
Collections.sort(ans,(ArrayList<Integer> a,ArrayList<Integer> b)->{return a.get(0).compareTo(b.get(0));});
return ans;
}
public ArrayList<Integer> getOdd(int mid,boolean even)
{
ArrayList<Integer> res = new ArrayList();
if(mid==sum)
{
return res;
}
int l = mid-1,r = mid+1;
if(even) ++l;
int sq = l+r+mid;
if(even) sq-=mid;
while(sq<=sum)
{
if(sq==sum)
{
for(int i=l;i<=r&&(i>0);++i)
{
if(i==0) continue;
res.add(i);
}
return res;
}
l--;r++;
sq+=(l+r);
}
return res;
}
}