算法提高之LeetCode刷题数据结构和算法分析

和为s的连续正数序列

2020-02-27  本文已影响0人  _阿南_

题目:

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

题目的理解:

这个还是找了下规律,不然无从下手:

  1. 分析出只有奇数才会满足要求,偶数不行。
  2. 生成整数的一半到2的数组
  3. 并根据数组中元素A,获取A个连续的数
  4. 分A是否为偶数,进行连续的数不同取法

python实现

class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        if target < 3:
            return list()

        result = list()
        max = int(target / 2) + 1
        index_arr = sorted(range(2, max), reverse=True)

        for index in index_arr:
            middle = int(target / index)
            distance = int(index / 2)
            end = distance if index % 2 == 0 else distance + 1

            if index % 2 == 0:
                if middle - distance + 1 <= 0:
                    continue
                
                temp_index = range(middle - distance + 1, middle + end + 1)

                if sum(temp_index) == target:
                    result.append(list(temp_index))

            if middle - distance <= 0:
                continue

            temp_index = range(middle - distance, middle + end)
            if sum(temp_index) == target:
                result.append(list(temp_index))

        return result

提交

成功

代码感觉写的有点乱,但是看到成绩不错,突然就觉得代码也没有那么乱了。

// END 还是害怕社交,感觉陌生人都想谋害朕,哇哈哈

上一篇 下一篇

猜你喜欢

热点阅读