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.

Thought

1. Define a sum_list to store the sum of the previous subarray at different index.
2. Sort the sum_list and compare the difference between the neighboring items in the sorted sum_list.
3. Find the smallest difference and the neighboring items are the desired sum of the subarray.
4. Find the original index for these two sums.

Trap

Be careful that the index of the smaller one should plus 1 as the result.

Code

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
        # No challenge
        if len(nums) <= 1:
            return [0, 0]
        sum_list = [nums[0]]
        for num in nums[1:]:
            sum_list.append(num + sum_list[-1])
        sort_sum = sorted(sum_list)
        diff = sys.maxint
        index1 = 0
        index2 = 0
        for i in xrange(1, len(sort_sum)):
            if sort_sum[i] - sort_sum[i - 1] < diff:
                diff = sort_sum[i] - sort_sum[i - 1]
                num1 = sort_sum[i - 1]
                num2 = sort_sum[i]
        index = []
        for i in xrange(len(sum_list)):
            if num1 == sum_list[i] or num2 == sum_list[i]:
                index.append(i)
                if len(index) == 2:
                    break
        index1 = min(index) + 1
        index2 = max(index)
        return [index1, index2]