Subarray Sum Closest

Question

• lintcode: (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
O(nlogn) time

题解

题 Zero Sum Subarray | Data Structure and Algorithm 的变形题，由于要求的子串和不一定，故哈希表的方法不再适用，使用解法4 - 排序即可在 $$O(n \log n)$$ 内解决。具体步骤如下：

1. 首先遍历一次数组求得子串和。
2. 对子串和排序。
3. 逐个比较相邻两项差值的绝对值，返回差值绝对值最小的两项。

• reference

import sys
class Pair:

    def __init__(self, sum, index):
        self.sum = sum
        self.index = index


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):
        res = []
        if not nums:
            return res

        length = len(nums)
        if length == 1:
            return[0, 0]

        sums = [Pair(0, 0)]
        prev = 0
        for i in range(1, length + 1):
            sums.append(Pair(prev + nums[i - 1], i))
            prev = sums[i].sum

        sums = sorted(sums, key=lambda pair: pair.sum)
        Closest = sys.maxint
        for i in range(1, length + 1):
            if Closest > sums[i].sum - sums[i - 1].sum:
                Closest = sums[i].sum - sums[i - 1].sum
                res = []
                tmp = [sums[i].index - 1, sums[i - 1].index - 1]
                tmp.sort()
                res.append(tmp[0] + 1)
                res.append(tmp[1])

        return res

sol = Solution()
nums = [-3, 1, 1, -3, 5]
sol.subarraySumClosest(nums)

• reference
• visualization

class Node:
    def __init__(self, _value, _pos):
        self.value = _value
        self.pos = _pos
    def __cmp__(self, other):
        if self.value == other.value:
            return self.pos - other.pos
        return self.value - other.value 
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
        s = []
        s.append(Node(0, -1))
        sum = 0
        for x in xrange(len(nums)):
            sum += nums[x]
            s.append(Node(sum, x))

        s = sorted(s)
        results= [0,0]
        ans = 1000000000000
        for i in xrange(len(s)-1):
            if s[i+1].value - s[i].value < ans or \
                s[i+1].value - s[i].value == ans and \
                min(s[i+1].pos, s[i].pos) + 1 < results[0]:
                ans = s[i+1].value - s[i].value
                results[0] = min(s[i+1].pos, s[i].pos) + 1          
                results[1] = max(s[i+1].pos, s[i].pos)

        return results
sol = Solution()
nums = [-3, 1, 1, -3, 5]
sol.subarraySumClosest(nums)