[leetcode 327]Count of Range Sum 原创解法

题目概述

原题链接

Given an integer array nums, return the number of range sums that lie in [lower, upper] inclusive.
Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j (i ≤ j), inclusive.

Example:
Given nums = [-2, 5, -1], lower = -2, upper = 2,
Return 3.
The three ranges are : [0, 0], [2, 2], [0, 2] and their respective sums are: -2, -1, 2.

O(N^2)解法

最直接的想法当然就是遍历求和了。但是这样是无法通过测试的。

class Solution3(object):
    def countRangeSum(self, nums, lower, upper):
        """
        :type nums: List[int]
        :type lower: int
        :type upper: int
        :rtype: int
        """

        sums = []

        for i in range(len(nums)):
            s = 0
            for j in range(i, len(nums)):
                s += nums[j]
                if lower <= s <= upper:
                    sums.append(s)
        return len(sums)

死亡凝视

必须要想出复杂度是Nlog(N)的算法才行。但是问题也很明显， 要想找出所有的s(i,j) for 0 <= i <= j < n　and lower <= s(i,j) <= upper 那必须要进行遍历啊，因此时间复杂度必须是N^2。 啊啊，实在想不出来了。

第二天，既然要求时间复杂度为NlogN那么就必然不能遍历求出s(i,j)，但是 题目要求的是求出Num(s(i,j)) for 0 <= i <= j < n　and lower <= s(i,j) <= upper ，也就是说给出个数就行，因此确实不一定要给出所有的s(i,j)。嗯，有点进展了。

第三天，排序算法的复杂度是NlogN，怎么才能依靠排序算法求出呢。难道对所有的 s(i,j)进行排序么？这样肯定不行。 能否使用老办法画图呢？这样好观察一下。但是仔细想了想，这是一个三维图。 纸上画不出来。 只好画一个二维图吧。下图是对数组[5,7,8,-2,1]画的二维表格。格子 中的数字就是s(i,j)。

我仔细的盯着看。我给这种解决问题的方式，起了 个名字——死亡凝视。看过The Big Bang的朋友可能记得Sheldon和Raj一起 工作的样子，就是一动不动的看着黑板上的公式，看上一整天。

嘿嘿，你们不要笑啊，我的方式差不多。只不过是盯着表格。这样的表格 其实我画了很多。但是只有这个我看出了规律。

看出来了么，三列带颜色的数字。是不是发现它们有相同的趋势呢？ 是的它们有相同的趋势。

如果没有看出来。我再画一个图。看看这三列数字和蓝色数字的关系。

是的。20 - 5 = 15，18 - 5 = 13，19 - 5 = 14。 假如上下区间为[12,18]，那么对于排序后的第一列[5,12,18,19,20]， 可以使用二分查找法找出上限的位置是2，下限的位置为1，个数为2。 那么第二列[7,15,13,14]在[12,18]的数字的个数为3。 怎么根据第一列排序后的数字求出呢。嗯，很简单。 我们把上下限加上5，变成17, 23，这样就可以发现[5,12,18,19,20]找出 个数为3。嗯，哈哈。真是不错。这样子，就不需要求出所有的s(i,j)了。

但是，别着急，还是有问题，我们需要在计算第二列的个数的之前，把第一列的数字中的5排除掉。 否则的话，如果区间是[-100,100]，那么我们就多计算了。

通过的代码

# python3.5
class Solution4(object):
    def countRangeSum(self, nums, lower, upper):
        """
        思路：对 list0 = [s(0,j) for j in (0,n)]先进行排序。
         list1 = [s(1,j) for j in (1,n)]，可以由 list0生成。

        :type nums: List[int]
        :type lower: int
        :type upper: int
        :rtype: int
        """
        if not nums:
            return 0
        else:
            result = 0
            n = len(nums)
            l = []
            l2 = []
            sum = 0
            for i in range(0, n):
                sum += nums[i]
                l.append((sum, i))
                l2.append((sum, i))
            l.sort()
            for i in range(0, n):
                if i > 0:
                    lower += nums[i - 1]
                    upper += nums[i - 1]
                lower_pos = self.find_lower(l, lower)
                upper_pos = self.find_uppper(l, upper)
                if lower_pos is not None and upper_pos is not None:
                    result += upper_pos - lower_pos + 1
                pos = self.find_lower(l, l2[i][0])
                l.pop(pos) # <-- 这里是个接近O(N)的操作

            return result

    def find(self, nums, target):
        n = len(nums)

        start = 0
        end = n
        mid = n // 2
        new_mid = None

        while 0 <= mid < n:
            if nums[mid][0] == target:
                break
            elif nums[mid][0] < target and mid + 1 < n and nums[mid + 1][0] > target:
                break
            elif nums[mid][0] < target:
                start = mid
                new_mid = (start + end) // 2
            elif nums[mid][0] > target:
                end = mid
                new_mid = (start + end) // 2
            if new_mid == mid:
                mid += 1
            else:
                mid = new_mid

        return mid if nums[mid][0] == target else mid + 1

    def find_lower(self, nums, lower):
        n = len(nums)
        if lower > nums[n - 1][0]:
            return None
        elif lower < nums[0][0]:
            return 0
        else:
            mid = self.find(nums, lower)
            while mid - 1 >= 0 and nums[mid - 1][0] == lower:
                mid -= 1
            return mid

    def find_uppper(self, nums, upper):
        n = len(nums)
        if upper > nums[n - 1][0]:
            return n - 1
        elif upper < nums[0][0]:
            return None
        else:
            mid = self.find(nums, upper)
            while mid < n - 1 and nums[mid + 1][0] == upper:
                mid += 1
            return mid if nums[mid][0] == upper else mid - 1

总结

排序操作的时间复杂度是O(NlogN)，而找出每列一列的个数的时间复杂度是O(logN) 因为一共有N列，所以时间复杂度为O(NlogN)，另外 我们在代码中使用了对List数据的非尾部的pop操作，这个操作的时间 复杂度接近O(N)，严格来说，我们的代码的时间复杂度还是O(N^2)。如果能够不使用这个操作。 我们的代码速度会更快。

l.pop(pos) # <-- 这里是个接近O(N)的操作