# 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
```
