【算法题】和为s的连续正数序列(Go解题)

69 阅读 0 评论 46 点赞

我是靠谱客的博主热情绿草，最近开发中收集的这篇文章主要介绍【算法题】和为s的连续正数序列(Go解题)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目

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

题目来源：https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/

解体思路：
建立两个指针l,r分别为符合条件序列的起点位置以及终点位置，根据求和公式： $\frac{( a + b ) * ( b - a + 1 )}{2}$ = sum，进行[l,r]区间求和结果判断

根据题意，初始状态为l = 1，r = 2（序列至少两个数，且为连续正整数序列）
当[l,r]区间的和等于target值时，表明找到了一个符合条件的序列，则将改区间的值新增为结果序列，且起始位置右移一位，
当[l,r]区间和大于target值时，表明区间值和过大，即以当前位置作为起始位置无符合条件的序列，则l右移一位，继续遍历
当[l,r]区间和小于target值时，表明区间值和过小，r右移一位，继续遍历
重复2~4步骤，直至l >= r，即[l,r]以及往后的区间已经不符合序列至少为两个数条件 (r - l + 1 ) >= 2 条件，结束遍历
返回结果res

此外，因为：
$\frac{( a + b ) * ( b - a + 1 )}{2}$ = $s u m$
=
${(a+b) * (b - a + 1)} = sum * 2$
所以，可以在进行遍历判断前把target*2，这可以让遍历求和公式减少每次求和除法运算，也避免了/2带来的结果可能为非整数而每次将结果强制转换为int型的操作，提高了一定的效率。

go代码

//双指针法
func findContinuousSequence(target int) [][]int {
    if target < 3 {
        return [][]int{}
    }

    var res [][]int
    l := 1
    r := 2
    target = target << 1 //这里用位移预算代替*号运算，左移1位，将target * 2
    for l < r {
        sum := (l + r) * (r - l + 1) //减少了每次求和除法运算，也避免了/2带来的结果可能为非整数而每次将结果强制转换为int型的操作
        if sum == target {
            subRes := make([]int, r - l + 1)
            k := 0
            for j := l; j <= r; j++ {
                subRes[k] = j
                k++
            }
            res = append(res, subRes)
            l++
        } else if sum < target {
            r++
        } else {
            l++
        }
    }
    return res
}