算法32--求出给定数组中某一段连续区间之和为某值的起始索引

给定一个数组以及一个目标数，求数组中一段连续的区间使得该区间元素之和为目标数。

例如num=[1,2,3,4,5] target=10  结果返回[0,3]

解法一：遍历所有情况  时间复杂度N2

def getSumIndex2(num=[1,2,3,4,5,6,7,8,9], target=30):
    for i in range(len(num)):
        sum = 0
        for j in range(i, len(num)):
            sum += num[j]
            if sum==target:
                print(i, j)
                return i, j
    return -1, -1

解法二：利用双指针i,j来维护一段连续区间，记录该区间的和sum:

如果sum==target  则返回i,j即可

如果sum<target,j++,更新sum

如果sum>target,i++,更新sum

def getSumIndex(num=[1,2,3,4,5,6,7,8,9], target=30):
    i = 0
    j = i
    sum = 0
    while j<len(num) and i<=j:
        if sum==target:
            return i, j-1
        while sum<target:
            sum += num[j]
            j += 1
        while sum>target:
            sum -= num[i]
            i += 1
    return -1, -1

最后

以上就是妩媚楼房为你收集整理的算法32--求出给定数组中某一段连续区间之和为某值的起始索引的全部内容，希望文章能够帮你解决算法32--求出给定数组中某一段连续区间之和为某值的起始索引所遇到的程序开发问题。

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