跳转至

面试题 57 - II. 和为 s 的连续正数序列

题目描述

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

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

 

示例 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 <= target <= 10^5

解法

方法一：双指针

我们可以使用双指针的方法，维护一个区间 \([l,.. r]\)，使得区间内的数之和 \(s\) 为 target，如果区间内的数之和小于 target，则右指针 \(l\) 右移，如果区间内的数之和大于 target，则左指针 \(l\) 右移，直到左指针到达 target 的一半为止。

时间复杂度 \(O(target)\)，忽略答案的空间消耗，空间复杂度 \(O(1)\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        l, r = 1, 2
        ans = []
        while l < r:
            s = (l + r) * (r - l + 1) // 2
            if s == target:
                ans.append(list(range(l, r + 1)))
                l += 1
            elif s < target:
                r += 1
            else:
                l += 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int[][] findContinuousSequence(int target) {
        int l = 1, r = 2;
        List<int[]> ans = new ArrayList<>();
        while (l < r) {
            int s = (l + r) * (r - l + 1) / 2;
            if (s == target) {
                int[] t = new int[r - l + 1];
                for (int i = l; i <= r; ++i) {
                    t[i - l] = i;
                }
                ans.add(t);
                ++l;
            } else if (s < target) {
                ++r;
            } else {
                ++l;
            }
        }
        return ans.toArray(new int[0][]);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        vector<vector<int>> ans;
        int l = 1, r = 2;
        while (l < r) {
            int s = (l + r) * (r - l + 1) / 2;
            if (s == target) {
                vector<int> t(r - l + 1);
                iota(t.begin(), t.end(), l);
                ans.emplace_back(t);
                ++l;
            } else if (s < target) {
                ++r;
            } else {
                ++l;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
func findContinuousSequence(target int) (ans [][]int) {
    l, r := 1, 2
    for l < r {
        s := (l + r) * (r - l + 1) / 2
        if s == target {
            t := make([]int, r-l+1)
            for i := range t {
                t[i] = l + i
            }
            ans = append(ans, t)
            l++
        } else if s < target {
            r++
        } else {
            l++
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * @param {number} target
 * @return {number[][]}
 */
var findContinuousSequence = function (target) {
    const ans = [];
    let l = 1;
    let r = 2;
    while (l < r) {
        const s = ((l + r) * (r - l + 1)) >> 1;
        if (s == target) {
            const t = [];
            for (let i = l; i <= r; ++i) {
                t.push(i);
            }
            ans.push(t);
            ++l;
        } else if (s < target) {
            ++r;
        } else {
            ++l;
        }
    }
    return ans;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
    public int[][] FindContinuousSequence(int target) {
        List<int[]> ans = new List<int[]>();
        int l = 1, r = 2;
        while (l < r) {
            int s = (l + r) * (r - l + 1) >> 1;
            if (s == target) {
                List<int> t = new List<int>();
                for (int i = l; i <= r; i++) {
                    t.Add(i);
                }
                l += 1;
                ans.Add(t.ToArray());
            } else if (s < target) {
                r += 1;
            } else {
                l += 1;
            }
        }
        return ans.ToArray();
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    func findContinuousSequence(_ target: Int) -> [[Int]] {
        var l = 1, r = 2
        var result = [[Int]]()

        while l < r {
            let sum = (l + r) * (r - l + 1) / 2
            if sum == target {
                var sequence = [Int]()
                for i in l...r {
                    sequence.append(i)
                }
                result.append(sequence)
                l += 1
            } else if sum < target {
                r += 1
            } else {
                l += 1
            }
        }

        return result
    }
}

评论