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

Tags: Easy Math Two Pointers

Links: https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/

---

输入一个正整数 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

---

class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        long long t = target;
        vector<vector<int>> res;

        long long mid = t / 2;
        for (long long m = 1; m <= mid; ++m) {
            int k = ((-2 * m - 1) + sqrt(4 * m * m  - 4 * m + 8 * t + 1)) / 2;
            if ((2 * m + k) * (k + 1) / 2 == t) {
                vector<int> tmp(k + 1);
                for (int i = 0; i <= k; ++i) {
                    tmp[i] = m + i;
                }
                res.push_back(tmp);
            }
        }

        return res;
    }
};

数学解法，等差数列求和，判断末尾项，检验总和是否相等，相等之后可以直接判断出序列长度，开一个数组，填入数字即可，注意只需要判断一半的数据即可。

双指针解法：

class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        vector<vector<int>> res;

       long long start = 1, end = 1;
       long long mid = target / 2;

       while (start <= mid) {
           long long sum = (start + end) * (end - start + 1) / 2;
           if (sum == target) {
               int k = end - start + 1;
               vector<int> tmp(k);
               for (int i = 0; i < k; ++i) {
                   tmp[i] = start + i;
               }
               res.push_back(tmp);
               ++start; ++end;
           }
           else if (sum < target) ++end;
           else ++start;
       }

        return res;
    }
};