leetcode-和为s的连续正数序列

84 阅读 0 评论 56 点赞

我是靠谱客的博主默默红酒，最近开发中收集的这篇文章主要介绍leetcode-和为s的连续正数序列，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目来自LeetCode，链接：和为s的连续正数序列。具体描述为：输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

示例1:

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

示例2:

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

这道题的话最naive的想法就是遍历以从1到target/2开头的一系列连续数字，这就不赘述了。

首先说一下我的做法，通过观察，可以发现凡是符合条件的序列都有以下特点：

数列长度为奇数的话，中间的数字刚好等于target除以数列长度；
数列长度为偶数的话，中间两个数的平均数为X.5=target÷数列长度（比如第一个例子有4.5=9÷2）。

所以根据这个，我们直接遍历可能的序列长度（也就是2到target的一半），并判断此序列长度下是否有满足条件的连续正数。时间复杂度为 $O (N)$ ，空间复杂度为 $O (1)$ 。

JAVA版代码如下：

class Solution {
    public int[][] findContinuousSequence(int target) {
        List<int[]> result = new LinkedList<>();
        for (int i = 2; i <= (target + 1) / 2; ++i) {
            if (i % 2 == 0 && target % i == i/2) {
                int smallerNum = target/i - i/2 + 1;
                if (smallerNum <= 0) {
                    break;
                }
                else {
                    int[] oneSolution = new int[i];
                    for (int j = 0; j < i; ++j) {
                        oneSolution[j] = smallerNum + j;
                    }
                    result.add(oneSolution);
                }
            }
            else if (i % 2 == 1 && target % i == 0) {
                int smallerNum = target/i - i/2;
                if (smallerNum <= 0) {
                    break;
                }
                else {
                    int[] oneSolution = new int[i];
                    for (int j = 0; j < i; ++j) {
                        oneSolution[j] = smallerNum + j;
                    }
                    result.add(oneSolution);
                }
            }
        }
        Collections.reverse(result);
        return result.toArray(new int[0][]);
    }
}

提交结果如下:

Python版代码如下：

class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        result = []
        for i in range(2, (target + 1) // 2 + 1):
            if i % 2 == 0 and target % i == i//2:       #如果可以由偶数个连续数字组成
                smallerNum = target//i - i//2 + 1
                if smallerNum <= 0:                     #接下来不再可能有符合的了，直接break
                    break
                else:
                    result.append([j for j in range(smallerNum, smallerNum + i)])
            elif i % 2 == 1 and target % i == 0:        #如果可以由奇数个连续数字组成
                smallerNum = target//i - i//2
                if smallerNum <= 0:
                    break
                else:
                    result.append([j for j in range(smallerNum, smallerNum + i)])
        return result[::-1]

提交结果如下:

这里再介绍另一种做法，考虑长度为n的数列，假设第一个数为 $a_{1}$ ，则符合条件的数列有
$target=na_{1}+frac{n(n-1)}{2}$

可得 $a_{1}=frac{target-frac{n(n-1)}{2}}{n}$ 。所以只需要遍历数列长度n，看是否有满足条件的 $a_{1}$ 即可。本质和上面的方法没有太大区别，只是在判断条件上没那么复杂了。

JAVA版代码如下：

class Solution {
    public int[][] findContinuousSequence(int target) {
        List<int[]> result = new LinkedList<>();
        for (int n = 2; n <= (target + 1) / 2; ++n) {
            int temp = target - n * (n - 1) / 2;
            if (temp % n == 0) {
                int first = temp / n;
                if (first > 0) {
                    int[] oneSolution = new int[n];
                    for (int i = 0; i < n; ++i) {
                        oneSolution[i] = first + i;
                    }
                    result.add(oneSolution);
                }
                else {
                    break;
                }
            }
        }
        Collections.reverse(result);
        return result.toArray(new int[0][]);
    }
}

提交结果如下:

Python版代码如下：

class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        #a1 = (target-n*(n-1)/2)/n
        n = 2
        first = 1
        result = []
        for n in range(2, (target + 1) // 2):
            temp = target - n * (n - 1) // 2
            if temp % n == 0:
                first = temp // n
                if first > 0:
                    result.append([i for i in range(first, first + n)])
                else:
                    break
        return result[::-1]

提交结果如下: