leetcode--面试题57 - II. 和为s的连续正数序列 (每日一题)

65 阅读 0 评论 43 点赞

我是靠谱客的博主愤怒糖豆，最近开发中收集的这篇文章主要介绍leetcode--面试题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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：利用队列进行操作

//创建一个队列
type Quee struct {
    count int
    head int
    tail int
    list []int
}

func NewQuee() *Quee {
    q := new(Quee)
    q.count = 0
    q.head = 0
    q.tail = 0
    q.list = make([]int,0)
    return q
}
//入列
func (q *Quee) Push(v int) {
    q.count++
    q.tail++
    q.list = append(q.list,v)
}
//出列
func (q *Quee) Pop() {
    if q.head >= q.tail{
        fmt.Println("队列已空")
    }
    q.head++
    q.count--
    q.list = q.list[q.head:]
    q.head = 0
}
//获得队头元素
func (q *Quee) GetHead () int {
    res := q.list[0]
    return res
}

func findContinuousSequence(target int) [][]int {
    //缩小查找区域
    res := make([][]int,0)
    mid := (target+1)/2 
    q := NewQuee()
    sum := 0
    for i:=1;i<=mid;i++ {
        q.Push(i)
        sum += i
        for sum > target {
            //队头出列
            sum -= q.GetHead()
            q.Pop()
        }
        if sum == target {
            //将队列中的元素存入数组中
            //队头出列
            //sum减去队头
            tmp := make([]int,0)
            for _,v := range q.list {
                tmp = append(tmp,v)
            }
            res = append(res,tmp)
            sum -= q.GetHead()
            q.Pop()
        } 
    }
    return res
}