腾讯面试题---最小运费问题

题目来源于牛客网网友分享的腾讯面经
题目描述：

给一串数列，这串数列有正有负，但是总和为0。
每个数xi代表一个村庄，正的表示村庄想卖出xi份水果，负的表示想买入xi份水果。
两相邻村庄间的距离是相同的，单位距离运送一份水果的运费均相同，每份都是k。
问，把每个村庄的需求和供给都解决掉需要的最少运送费是多少？

分析：
典型的双指针问题，若当前值nums[curr]大于0则从当前位置依次遍历找到一个小于0的值nums[j]进行交易，若当前值小于0则遍历找到一个大于0的值进行交易，当前值等于0则curr自增1.

def trade(nums,k=1):
    n = len(nums)
    sum_ = 0
    if n<2:return 0
    curr = 0
    j=1
    
    while curr<n-1:
        while nums[curr]<0:    
            while nums[j]<=0:
                j+=1
            if nums[curr]+nums[j]>=0:
                sum_+=k*(j-curr)*abs(nums[curr])
                nums[j] = nums[curr]+nums[j]
                nums[curr]=0
            else:
                sum_+=k*(j-curr)*nums[j]
                nums[curr] = nums[curr]+nums[j]
                nums[j]=0
        while nums[curr]>0:    
            while nums[j]>=0:
                j+=1
            if nums[curr]+nums[j]>=0:
                sum_+=k*(j-curr)*abs(nums[j])
                nums[curr] = nums[curr]+nums[j]
                nums[j]=0
            else:
                sum_+=k*(j-curr)*nums[curr]
                nums[j] = nums[curr]+nums[j]
                nums[curr]=0
        while curr<n-1 and nums[curr]==0:
            curr+=1
        j=curr+1
    return sum_

简单的测试样例

输入：[-1,2,-3,2,-2,3,-1]，输出：7
输入：[-5,2,-3,2,-2,3,2,2,-1]，输出：29