求连续子数组和等于给定目标值的区间--面试题

题目

给定n个数和一个target，输出连续区间和为target的所有区间
写代码的时候遇到的问题

1. 保存区间内元素和，区间变化加减操作即可，而不是每次对区间求和，这样时间复杂度就是O(n)了，否则是O(n^2)，因为还要遍历区间内部元素
2. 如果初始化元素和为0，样例，arr = [4] ，target = 4，应该返回[0,0]，出错。因此，初始化为数组第一个元素
3. j循环向后加时，防止越界；当区间和等于target，再向后遍历，可以i+或j+，但是j+可能会越界，因此选择i+
4. 最外面的while条件，i <= j and 这个条件不需要，如果加上，[3,1,2,5,7,10]，target=1 出错

参考：http://legendtkl.com/2014/04/26/array-problem-trick/

代码

def findsum(arr, target):
    i,j = 0,0
    ans = []
    tempsum = arr[0]
    while  j < len(arr): 
        while j < len(arr)-1 and tempsum < target:
            j +=1
            tempsum += arr[j]
        if tempsum == target:
            ans.append([i,j])
            tempsum -= arr[i]
            i += 1
        elif tempsum > target:
            tempsum -= arr[i]        
            i += 1
    return ans

if __name__ == "__main__":
    arr = [1,1,2,2,1,1,3,4,5]
    target = 4
    print(findsum(arr,target))

最后

以上就是无辜飞机为你收集整理的求连续子数组和等于给定目标值的区间--面试题的全部内容，希望文章能够帮你解决求连续子数组和等于给定目标值的区间--面试题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。