Subarray Sum Closest

Question

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

O(nlogn) time

Analysis

跟subarray sum类似，用一个array存从0到i的sum,然后sort一下，相邻两个找最小的差值

Thoughts

find subarray with given target subsequence closest to k

注意点

• empty array
• array with only one element
• 要return的是index而不是最小的差值，所以还要到原来的array中找到index,还有两个index的大小问题

Solution

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 not nums:
            return None
        if len(nums) == 1:
            return [0,0]
        sums = [0 for i in range(len(nums))]
        sums[0] = nums[0]
        for i in range(1, len(nums)):
            sums[i] = sums[i-1] + nums[i]

        sortedSums = list(sums)
        sortedSums.sort()

        minDiff = sys.maxint
        for i in range(1, len(sortedSums)):
            if sortedSums[i] - sortedSums[i-1] < minDiff:
                minDiff = sortedSums[i] - sortedSums[i-1]
                num1 = sortedSums[i-1]
                num2 = sortedSums[i]
        index1 = sums.index(num1)
        index2 = sums.index(num2)
        if index1 > index2:
            tmp = index1
            index1 = index2 + 1
            index2 = tmp
        else:
            index1 = index1 + 1
        return [index1, index2]