LintCode Q138 Subarray Sum in Python

  • Jinhai ZHOU
  • 3 Minutes
  • 2016年12月18日
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
"""
@param nums: A list of integers
@return: A list of integers includes the index of the first number
and the index of the last number
"""
def subarraySum(self, nums):
# write your code here
# assume input nums has at least 2 elements
# assume we can find this pattern in input array
# time complexity:
prefix_sum = [0] * len(nums) # prefix sum are not necessary
hash_map = {}
prefix_sum[0] = nums[0]
hash_map[prefix_sum[0]] = 0
for i in xrange(1, len(nums)):
prefix_sum[i] = prefix_sum[i - 1] + nums[i]
if prefix_sum[i] == 0:
return [0, i]
else:
if prefix_sum[i] in hash_map:
return [hash_map[prefix_sum[i]] + 1, i]
else:
hash_map[prefix_sum[i]] = i
return [0, 0] # when input nums = [0]
知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。