LeetCode 面試題57 - II. 和為s的連續(xù)正數(shù)序列 [簡(jiǎn)單]

輸入一個(gè)正整數(shù) target 石挂，輸出所有和為 target 的連續(xù)正整數(shù)序列（至少含有兩個(gè)數(shù)）儿惫。

序列內(nèi)的數(shù)字由小到大排列副瀑，不同序列按照首個(gè)數(shù)字從小到大排列晰搀。

來(lái)源：力扣（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：

暴力法：每個(gè)都進(jìn)行嘗試蕉拢，然后把符合條件的數(shù)據(jù)存儲(chǔ)到集合中去

解法2：

數(shù)學(xué)法：a為首項(xiàng)，共n項(xiàng)刻两，間距為1
a -> a + n -1 增蹭，即 target = (a + a + n -1)n/2

解法3：

算法是先找到符合的連續(xù)的2個(gè)數(shù)之和，然后符合的連續(xù)3個(gè)數(shù)磅摹，這樣子遞增的滋迈。例如9，先找符合的連續(xù)兩個(gè)數(shù)是4+5=4+(4+1)户誓，連續(xù)的三個(gè)數(shù)是2+3+4=2+(2+1)+(2+2)饼灿。難點(diǎn)是，我們能如何找到連續(xù)兩個(gè)數(shù)開頭的4和連續(xù)三個(gè)數(shù)的2帝美，我們就可以根據(jù)開頭的數(shù)自增就可以了碍彭。

設(shè)第一個(gè)值為a，一共有n個(gè)數(shù)，那么 ((a+a+n-1)/2)n=target, 推導(dǎo)得 a=(target-n(n-1)/2)/n, n(n-1)/2 是1到n-1的和硕旗，所以要target-=i++，然后就是一個(gè)個(gè)是n了女责。

代碼實(shí)現(xià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[][]{};
        }
        // 數(shù)學(xué)解法，太牛逼了
        // a為首項(xiàng)抵知，共n項(xiàng)墙基，間距為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][]);
    }

    /**
     * 這就有點(diǎn)詭異刷喜，在我本地 IDEA 可以通過(guò)残制，但是LeetCode 就不能通過(guò)
     */
    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][]);
    }
}