Continuous Subarray Sum

应该说这道题O(n^2)和O(n)的算法都不是很难想，关键在于看出用DP来解这个问题，首先是O(n^2)的算法，只要注意处理k等于0的情况就好了，其他跟LIS没有区别

class Solution(object):
    def checkSubarraySum(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: bool
        """
        n = len(nums)
        dp = [0] * (n + 1)

        for i in xrange(1, n + 1):
            dp[i] = dp[i - 1] + nums[i - 1]
            for j in xrange(i - 2, -1, -1):
                if k == 0 and dp[i] == dp[j]:
                    return True
                if k != 0 and (dp[i] - dp[j]) % k == 0:
                    return True


        return False

经验之谈：利用哈希表来做前缀查询的题目，一般都需要加上一个0：-1这样的键值对

这里主要是要考虑把k等于0的额外处理写的简洁

class Solution(object):
    def checkSubarraySum(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: bool
        """
        n = len(nums)
        store = {0:-1}
        tmp = 0
        for i in xrange(n):
            tmp += nums[i]
            if k != 0:
                tmp %= k
            if tmp in store:
                if i - store[tmp] > 1:
                    return True
            else:
                store[tmp] = i
        return False