LintCode 139. Subarray Sum Closest

题目

思路

这个题做的好累o(╥﹏╥)o
定义PrefixSum[i]=A[0]+A[1]+…A[i−1],PrefixSum[0]=0$PrefixSum[i]=A[0]+A[1]+\dots A[i-1],PrefixSum[0]=0$
则Sum(i j)=PrefixSum[j+1]−PrefixSum[i]$Sum(ij)=PrefixSum[j+1]-PrefixSum[i]$
1.得到PrefixSum
2.把PrefixSum从小到大排序
3.找到PrefixSum[i]−PrefixSum[i−1]$PrefixSum[i]-PrefixSum[i-1]$的最小值

代码

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 subarraySumClosest(self, nums):
        # write your code here
        if len(nums) == 1: return [0, 0]
        res_list = []
        res_list.append(0)
        res_list.append(2)
        sub_sum = []
        sub_sum.append([0, 0])
        sum = 0
        for i, v in enumerate(nums):
            sub_sum.append([sum + v, i + 1])
            sum += v
        sub_sum.sort(key = lambda x: x[0])
        minNum = 99999999
        sum = 0
        for i, v in enumerate(sub_sum):
            if i == 0: continue
            if minNum > (v[0] - sub_sum[i - 1][0]):
                minNum = v[0] - sub_sum[i - 1][0]
                res_list[0] = min(v[1] - 1, sub_sum[i - 1][1] - 1) + 1
                res_list[1] = max(v[1] - 1, sub_sum[i - 1][1] - 1)
        return res_list