剑指offer Two Pointers

剑指offer-和为s的连续正数序列

Posted by franki on May 21, 2021

和为s的连续正数序列

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

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

示例

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

思路

利用双指针，不断控制指针的移动，来收缩查找的范围，直到找到所有符合要求的结果

代码

/**
 * @param {number} target
 * @return {number[][]}
 */
var findContinuousSequence = function(target) {
    let mid = (1 + target) >> 1;
    let small = 1;
    let big = 2;
    const result = [];
    let curSum = small + big;
    while (small < mid) {
        if (curSum === target) {
            result.push(cal(small, big));
        }
        while(curSum > target && small < mid) {
            curSum -= small;
            small++;
            if (curSum === target) {
                result.push(cal(small, big));
            }
        }
        big++;
        curSum += big;
    }

    return result;
};

function cal(start, end) {
    const res = [];
    for (let i = start; i<=end; i++) {
        res.push(i);
    }
    return res;
}

复杂度分析:

  • 时间复杂度: O(N^2)
  • 空间复杂度：O(N)
CATALOG
    FEATURED TAGS
    前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析 生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python
    FRIENDS