(双指针) 剑指 Offer 57 - II. 和为s的连续正数序列 —

(双指针) 剑指 Offer 57 - II. 和为s的连续正数序列 ——【Leetcode每日一题】

❓ 剑指 Offer 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$

💡思路：双指针

我们用两个指针 i 和 j 表示当前枚举到的以 i 为起点到 j 的区间，sum 表示 [i,j] 的区间和，由连续正数,所以求和公式为：(起始 i = 1, j = 2) $\textit{sum}=\frac{(l+r) \times (r-l+1)}{2}$
共有三种情况：

sum == target
- 则说明我们找到了以 i 为起点得合法解 [i,j] ，我们需要将 [i,j] 的序列放进答案数组；
- 我们知道以 i 为起点的合法解最多只有一个，所以需要枚举下一个起点，往大的方向走，此时 i += 2 ， j++；
sum < target
- 指针 j 向右移动，使得 sum 增大，即 j++;
sum > target
- 指针 i 向右移动，使得 sum 减小，即 i++。

终止条件即为 i >= j 或者指针 j 移动到了 $\frac{\textit{target + 1}}{2}$ 的位置，导致 i < j 的时候区间和始终大于 target 。

🍁代码：(C++、Java)

C++

class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        vector<vector<int>> ans;
        if(target < 2) return ans;
        for(int i = 1, j = 2; i < j && j <= (target + 1) / 2; ){
            int sum = (i + j) * (j - i + 1) / 2;
            if(sum == target){
                vector<int> temp;
                for(int k = i; k <= j; k++) temp.push_back(k);
                ans.push_back(temp);
                i += 2;
                j++;
            }else if(sum < target){
                j++;
            }else{
                i++;
            }
        }
        return ans;
    }
};

Java

class Solution {
    public int[][] findContinuousSequence(int target) {
        List<int[]> ans = new ArrayList<int[]>();
        if(target < 2) return new int[0][0];
        for(int i = 1, j = 2; i < j && j <= (target + 1) / 2; ){
            int sum = (i + j) * (j - i + 1) / 2;
            if(sum == target){
                int[] temp = new int[j - i + 1];
                for(int k = i; k <= j; k++) temp[k - i] = k;
                ans.add(temp);
                i += 2;
                j++;
            }else if(sum < target){
                j++;
            }else{
                i++;
            }
        }
        return ans.toArray(new int[ans.size()][]);
    }
}

🚀 运行结果：

在这里插入图片描述

🕔 复杂度分析：

时间复杂度： $O (t a r g e t)$ ，由于两个指针移动均单调不减，且最多移动 $\frac{\textit{target + 1}}{2}$ 次，即方法一提到的枚举的上界，所以时间复杂度为 $O (t a r g e t)$ 。
空间复杂度： $O (1)$ ，除了答案数组只需要常数的空间存放若干变量。