LeetCode Notes: Sequence of Consecutive Positive Numbers Whose Sum Is S

#leetcode

Question

Input a positive integer target, and output all consecutive positive integer sequences (containing at least two numbers) whose sum is target.

The numbers in the sequence are arranged from smallest to largest, and different sequences are arranged from smallest to largest according to the first number.

Example 1:

Input: target = 9

Output: [[2,3,4],[4,5]]

Example 2:

Input: target = 15

Output: [[1,2,3,4,5],[4,5,6],[7,8]]

limit:

-1 <= target <= 10^5

Solution

Analysis:

Using the idea of ​​sliding window

  1. Starting from 1 to accumulate the sum of the numbers of the sliding window, we call it the sum
  2. When moving the window, if the sum does not reach the target value, move the right boundary to the right to increase the sum, and then loop to find the next matching value
  3. When moving the window, the sum is exactly equal to the target value, and the array of sliding windows is stored. At this time, you can no longer move the right boundary to the right, because once the right boundary is moved, the sum must exceed the target value and cannot match the target value again. So we should move the left border to the right, and then loop to find the next matching value
  4. When moving the window, the sum exceeds the target value, and the right boundary obviously cannot continue to move to the right. Because this is the same as the situation mentioned above, the target cannot be matched again afterwards, so we should also move the left boundary to the right, and then loop to find the next A matching value

Code:

/**
 * @param {number} target
 * @return {number[][]}
 */

var findContinuousSequence = function(target) {
    let start = 1 //The starting position of the sliding window, which is the left boundary
    let end = 1 //The end position of the sliding window, which is the right boundary
    let sum = 0 //The sum of the numbers of the sliding window, used to compare with the target
    result = [] //Result array

    // Start position, once start is larger than half of target, start + start + 1 will exceed the size of target, no need to recycle
    while(start <= target / 2){
        // Did not reach the target value, continue to search
        if(sum <target){
            sum += end
            end += 1
        }
        // Exceed the target value, move the left boundary to the right
        else if(sum> target){
            sum -= start
            start += 1
        }
        // Equal to the target value, store it, and move the left boundary to the right
        else{
            //Get the incrementing array through the start and end values, such as: 2,4 => [2,3]
            let res = [...new Array(end).keys()].slice(start)
            result.push(res)

            sum -= start
            start += 1

        }
    }

    return result

};

Reference

Comments