算法长征（1）数组

发表于 更新于 分类于 ， 阅读次数： 本文字数： 709 阅读时长 ≈ 1 分钟

输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。【分治】【==大数打印解法==】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def printNumbers(self, n: int) -> List[int]:
        def dfs(index, num, digit):
            if index == digit:
                res.append(int(''.join(num)))
                return
            for i in range(10):
                num.append(str(i))
                dfs(index + 1, num, digit)
                num.pop()
        res = []
        for digit in range(1, n + 1):
            for first in range(1, 10):
                num = [str(first)]
                dfs(1, num, digit)
        
        return res

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的==子数组==的个数 。

  • -1000 <= nums[i] <= 1000
  • 前缀和 + 哈希表优化
1
2
3
4
5
6
7
8
9
10
class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        dic = collections.defaultdict(int)
        dic[0] = 1
        res = preNum = 0
        for i in range(len(nums)):
            preNum += nums[i]
            res += dic[preNum - k]
            dic[preNum] += 1
        return res