题解 | #和为S的连续正数序列#

import java.util.ArrayList;
 /**连续正数序列等于某一个值即等差数列和等于某一个值
     * 等差数列求和公式为(a1 + an) * n / 2 = sum
     * 我们假设序列长度为x，起始值为i那么此公式可转换为方程：(i + i + x - 1) * x / 2 = sum
     * 整理后可得x^2 + (2i - 1)x - 2sum = 0明显是一个一元2次方程式
     * 求输出和为s的连续正整数序列 我们可以从1开始找，找到(s + 1) / 2即能找到所有连续子序列(为什么是(s + 1) / 2可以好好想想 比如11可以是[5, 6]))
     * 因此我们可以在1~ s / 2中所有令方程式有正整数解的i即为连续正整数序列的头
     * @param sum
     * @return
     */
public class Solution {
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
         ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
        if (sum <= 1){
            return lists;
        }
        int end = (sum + 1) / 2;
        for(int i = 1; i < end; i++){
            int num = solve(1, 2 * i - 1, -2 * sum);
            if (num != 0){//找到正整数解 加入此连续序列
                ArrayList<Integer> list = new ArrayList<>();
                for (int j = i; j < i + num; j++){
                    list.add(j);
                }
                lists.add(list);
            }
        }
        return lists;
    }
    
  /**
     * 因为a > 0 b > 0
     * 所以正整数解只可能出现在(-b + Math.sqrt(delta)) / (2 * a)这个计算式里
     * @param a
     * @param b
     * @param c
     * @return
     */
    public int solve(int a, int b, int c){//a > 0, b > 0
        double delta = Math.pow(b, 2) - 4 * a * c;
        if (delta < 0){//delta < 0直接返回0
            return 0;
        }
        int res;
        double num;
        num = (-b + Math.sqrt(delta)) / (2 * a);
        res = (int) num;
        if (res == num && res > 0){//res是正整数返回
            return res;
        }
        return 0;//无正整数解
    }
}