卖萌的弱渣

I am stupid, I am hungry.

Subarry Sum

Subarray Sum

Given an integer array, find a subarray where the sum of numbers is zero. Your code should return the index of the first number and the index of the last number.

Example

Given [-3, 1, 2, -3, 4], return [0, 2] or [1, 3].

Note

There is at least one subarray that it’s sum equals to zero.

Solution

  • Bruce Force: O(N2)
(Subarray-Sum.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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 subarraySum(self, nums):
        # write your code here
        result = []
        if nums == None or len(nums) == 0:
            return result

        for i in range(len(nums)):
            # [1,2,3,0] => [3,3] is correct
            if nums[i] == 0:
                return [i,i]
            sum = nums[i]
            for j in range(i+1, len(nums)):
                if sum + nums[j] == 0:
                    result.append(i)
                    result.append(j)
                    return result
                else:
                    sum += nums[j]
        return result
  • Hash table: O(N)
    • Hash Table: {[sum: index+1]}
    • You calculate the sum of substrings and maintain the hash table, if you find the sum appear again, you find the substring
    • For example: [hash-table[sum],x,x,x,i] then[x,x,x,i] is the string
    • Consider when sum==0, we have to initialize the hash-table with {[0:0]}
(Subarray-Sum-hashtable.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

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 subarraySum(self, nums):
        # write your code here
        # hash_map: {sum: index}
        hash_map = dict()
        hash_map[0] = 0
        result = []
        if nums == None or len(nums) == 0:
            return result

        sum = 0
        for i in range(len(nums)):
            # case <x, x, x, 0, x, x>
            if nums[i] == 0:
                result.append(i)
                result.append(i)
                return result

            sum += nums[i]
            # if you find sum again
            # <hash_map[sum],x,x,x,i> is the substring you are looking for
            if(hash_map.has_key(sum)):
                result.append(hash_map[sum])
                result.append(i)
                return result
            else:
                hash_map[sum] = i+1
        return result