LeetCode 每日一题 [18] 和为s的连续正数序列

LeetCode 面试题57 - II. 和为s的连续正数序列 [简单]

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。

序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof

示例 1：

输入：target = 9
输出：[[2,3,4],[4,5]]

示例 2：

输入：target = 15
输出：[[1,2,3,4,5],[4,5,6],[7,8]]

限制：

1 <= target <= 10^5

题目分析：

解法1：

暴力法：每个都进行尝试，然后把符合条件的数据存储到集合中去

解法2：

数学法：a为首项，共n项，间距为1
a -> a + n -1 ，即 target = (a + a + n -1)n/2

解法3：

算法是先找到符合的连续的2个数之和，然后符合的连续3个数，这样子递增的。例如9，先找符合的连续两个数是4+5=4+(4+1)，连续的三个数是2+3+4=2+(2+1)+(2+2)。难点是，我们能如何找到连续两个数开头的4和连续三个数的2，我们就可以根据开头的数自增就可以了。

设第一个值为a，一共有n个数，那么 ((a+a+n-1)/2)n=target, 推导得 a=(target-n(n-1)/2)/n, n(n-1)/2 是1到n-1的和，所以要target-=i++，然后就是一个个是n了。

代码实现

public class LeetCode_18_ContinuousPositiveSequenceWithSumS {
    public static void main(String[] args) {
        int[][] cs = findContinuousSequence(9);
        int[][] cs2 = findContinuousSequence02(9);
        for (int i = 0; i < cs.length; i++) {
            System.out.println(Arrays.toString(cs[i]));
        }
        System.out.println("==========================");
        for (int i = 0; i < cs2.length; i++) {
            System.out.println(Arrays.toString(cs[i]));
        }
    }

    public static int[][] findContinuousSequence03(int target) {
        // 双指针，从前往后
        if (target <= 2) {
            return new int[][]{};
        }
        // 数学解法，太牛逼了
        // a为首项，共n项，间距为1
        // a -> a + n -1 ，即 target = (a + a + n -1)n/2
        List<int[]> res = new ArrayList<>();
        int a;
        for (int n = 2; n <= target; n++) {
            if ((2 * target - n * (n - 1)) % (2 * n) == 0) {
                a = (2 * target - n * (n - 1)) / (2 * n);
                if (a <= 0) {
                    break;
                }
                int[] cur = new int[n];
                for (int i = 0; i < n; i++) {
                    cur[i] = a + i;
                }
                res.add(cur);
            }
        }
        Collections.reverse(res);
        return res.toArray(new int[0][]);
    }

    /**
     * 这就有点诡异，在我本地 IDEA 可以通过，但是LeetCode 就不能通过
     */
    public static int[][] findContinuousSequence02(int target) {
        if (target <= 2) {
            return new int[][]{};
        }
        ArrayList<int[]> result = new ArrayList<>();
        int i = 1;
        while (target > 0) {
            target -= i++;
            if (target > 0 && target % i == 0) {
                int[] array = new int[i];
                for (int k = target / i, j = 0; k < target / i + 1; k++, j++) {
                    array[j] = k;
                }
                result.add(array);
            }
        }
        Collections.reverse(result);
        return result.toArray(new int[0][]);
    }

    /**
     * 暴力法
     */
    public static int[][] findContinuousSequence(int target) {
        List<int[]> res = new ArrayList<>();
        if (target <= 2) {
            return new int[][]{};
        }
        for (int i = 1; i < target / 2 + 1; i++) {
            int temp = target;
            int count = i;
            while (temp > 0) {
                temp = temp - count;
                count++;
            }
            if (temp == 0) {
                int[] arr = new int[count - i];
                int a = i;
                for (int j = 0; j < arr.length; j++) {
                    arr[j] = a;
                    a++;
                }
                res.add(arr);
            }
        }
        return res.toArray(new int[0][]);
    }
}