139. Subarray Sum Closest Given an integer array, find a subarray with sum closest to zero. Return the indexes of the first number and last number.

Example

Given [-3, 1, 1, -3, 5], return [0, 2], [1, 3], [1, 1], [2, 2] or [0, 4].

Challenge: do it in O(nlogn) time.

Solutions

Stpe 1, build the prefixSum array.

Step 2, problem has been converted into “in a sorted list, finding ‘two sum’ that closest to k” problem

import sys
from collections import namedtuple

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):
        # build prefixSum array

        Pair = namedtuple("Pair", "sum idx")
        preSum = [Pair(0, 0)] * (len(nums) + 1)
        for i in xrange(1, len(preSum)):
            preSum[i] = Pair(preSum[i - 1].sum + nums[i - 1], i)
        
        preSum.sort(key=lambda x: x.sum)
    
        maxDist = sys.maxint
        ret = None
        for i in xrange(1, len(preSum)):
            if (preSum[i].sum - preSum[i - 1].sum) < maxDist:
                maxDist = preSum[i].sum - preSum[i - 1].sum
                ret = [preSum[i].idx - 1, preSum[i - 1].idx - 1]
                
        ret.sort()
        ret[0] += 1
        return ret
    
    # Total Runtime: 4089 ms
    # 100% test cases passed.