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].

Solution

the different is equal to 0 , it's to check duplicated value in array but for this one we could know we can do a sorting to sum array then grap the

解题思路：

解题的重点就是位置i的Sum。

for other question sum close to zero means, Sum[i]~ i+1 Sum[j] and SUM[i] = SUM[j] , so we also know for this question , we can simple sort the SUM[i] array and find the close one.

相比于Subarray Sum问题，这里同样可以记录下位置i的sum，存入一个数组或者链表中，按照sum的值sort，再寻找相邻两个sum差值绝对值最小的那个，也就得到了subarray sum closest to 0。

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

首先遍历一次数组求得子串和。

对子串和排序。

逐个比较相邻两项差值的绝对

值，返回差值绝对值最小的两项。

为什么加1？ 跟零的那个异曲同工，都是下一个开始然后到后面的索引趋近于0

results[0] = min(s[i+1].pos, s[i].pos) + 1

results[1] = max(s[i+1].pos, s[i].pos)

class Node:
    def __init__(self, _value, _pos):
        self.value = _value
        self.pos = _pos

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
        result = []
        n = len(nums)
        s = []
        s.append(Node(0, -1))
        sum = 0
        for i in range(n):
            sum += nums[i]
            s.append(Node(sum, i))

        s = sorted(s, key = lambda node: node.value)

        results= [0,0]
        ans = sys.maxsize
        for i in xrange(len(s) - 1):
            if s[i+1].value - s[i].value < ans :
                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