327. Count of Range Sum

mj 发布于2019-08-14 17:34 / 298人阅读

摘要：题目链接这题实际就是给定范围内的，的方法。注意一开始把加进去，考虑结果是的情况，还有要用型，以免会还是可以来做，要统计范围内的个数，就是用。

327. Count of Range Sum

题目链接：https://leetcode.com/problems...

这题实际就是给定范围内的range sum，divide and conquer的方法。一路计算prefixSum[0:i]，并把结果放进tree里面，然后计算到prefixSum[0:j+1]的时候，找tree里面有没有满足条件的prefixSum[0:i]，这里的条件是lower <= sum[0:j+1] - sum[0:i] <= upper，那么可知sum[0:j+1] - upper <= sum[0:i] <= sum[0:j+1] - lower，那么这个就一个recursion就好了。注意一开始把0加进去，考虑结果是sum[0:j]的情况，还有要用long型，以免sum会overflow

public class Solution {
    public int countRangeSum(int[] nums, int lower, int upper) {
        int n = nums.length;
        if(n == 0) return 0;
        // binary search tree
        Node root = new Node(0);
        int res = 0;
        long prefixSum = 0;
        for(int i = 0; i < n; i++) {
            prefixSum += nums[i];
            res += findNumInBound(root, lower, upper, prefixSum);
            insert(root, prefixSum);
        }
        return res;
    }
    
    private int findNumInBound(Node node, long low, long up, long sum) {
        // base case
        if(node == null) return 0;
        // range: sum - up <= node.val <= sum - low
        if(node.val < sum - up) return findNumInBound(node.right, low, up, sum);
        else if(node.val > sum - low) return findNumInBound(node.left, low, up, sum);
        else return 1 + findNumInBound(node.left, low, up, sum) + findNumInBound(node.right, low, up, sum);
    }
    
    private void insert(Node node, long value) {
        while(node != null) {
            if(node.val > value) {
                if(node.left == null) {
                    node.left = new Node(value);
                    break;
                }
                node = node.left;
            }
            else {
                if(node.right == null) {
                    node.right = new Node(value);
                    break;
                }
                node = node.right;
            }
        }
    }
    
    class Node {
        long val;
        Node left;
        Node right;
        Node(long val) { this.val = val; }
    }
}

还是可以binary index tree来做，要统计sum[0:j+1] - upper <= sum[0:i] <= sum[0:j+1] - lower范围内的个数，就是用sum。参考博客：
http://bookshadow.com/weblog/...

public class Solution {
    public int countRangeSum(int[] nums, int lower, int upper) {
        int n = nums.length;
        if(n == 0) return 0;
        // prefix array
        long[] prefixSum = new long[n];
        for(int i = 0; i < n; i++) {
            prefixSum[i] = (i > 0 ? prefixSum[i-1] : 0) + nums[i];
        }
        long[] sorted = Arrays.copyOf(prefixSum, prefixSum.length);
        Arrays.sort(sorted);
        // binary index tree
        map = new HashMap();
        int idx = 1;
        for(long sum : sorted) {
            if(!map.containsKey(sum)) map.put(sum, idx++);
        }
        // build tree
        BIT t = new BIT(idx);
        int res = 0;
        for(int i = 0; i < n; i++) {
            int l = binarySearch(sorted, prefixSum[i] - upper - 1);
            int r = binarySearch(sorted, prefixSum[i] - lower);
            res += t.sum(r) - t.sum(l);
            if(prefixSum[i] >= lower && prefixSum[i] <= upper) res += 1;
            t.add(map.get(prefixSum[i]), 1);
        }
        return res;
    }
    Map map;
    // find the last element <= val
    private int binarySearch(long[] arr, long val) {
        int l = 0, r = arr.length - 1;
        while(l < r) {
            int mid = l + (r - l) / 2 + 1;
            if(arr[mid] <= val) l = mid;
            else r = mid - 1;
        }
        if(arr[l] > val) return 0;
        return map.get(arr[l]);
    }
    
    class BIT {
        int n;
        int[] tree;
        BIT(int n) { this.n = n; tree = new int[n]; }
        
        protected int sum(int i) {
            int res = 0;
            while(i > 0) {
                res += tree[i];
                i -= i & -i;
            }
            return res;
        }
        
        protected void add(int i, int val) {
            while(i < n) {
                tree[i] += val;
                i += i & -i;
            }
        }
    }
}

云服务器服务器托管 range() Range Count sum

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66674.html

leetcode327. Count of Range Sum

摘要：接着计算所有子数组中元素的和，并判断是否位于数值区间内。因此，在对左右子数组进行排序后，以左子数组中的每一位作为开头，在右子数组中找到满足和区间的第一个值，和超过区间的第一个值。则二者的差即为横穿左右的满足条件的子数组个数。题目要求 Given an integer array nums, return the number of range sums that lie in [lo...

miya 2019-08-16 16:47 评论0 收藏0
几个有趣的算法题目

摘要：统计元素个数排序第一步用来枚举和的大小，由题目可知，数组的长度。时间复杂度为数组长度，排序的时间为，枚举时间为，枚举时间为跨度，枚举全部元素时间为，因此算法的时间上界为实际情况下，由于剪枝等操作的存在，应优于这个时间。本文首发 http://svtter.cn 最接近的数字题目一个K位的数N $$ (Kleq2000，Nleq10^{20}) $$ 找出一个比N大且最接近的数，这...

honhon 2019-07-30 14:56 评论0 收藏0
SICP Python 描述 2.3 序列

摘要：序列不是特定的抽象数据类型，而是不同类型共有的一组行为。不像抽象数据类型，我们并没有阐述如何构造序列。这两个选择器和一个构造器，以及一个常量共同实现了抽象数据类型的递归列表。 2.3 序列来源：2.3 Sequences 译者：飞龙协议：CC BY-NC-SA 4.0 序列是数据值的顺序容器。不像偶对只有两个元素，序列可以拥有任意（但是有限）个有序元素。序列在计算机科学中...

AlexTuan 2019-07-25 10:43 评论0 收藏0
315. Count of Smaller Numbers After Self

摘要：题目链接的题，用来做，这种求有多少的题一般都是。里多加一个信息表示以为的节点数。也可以做，因为是统计有多少的，其实就是求从最小值到的。的是，要做一个映射，把的值映射到之间。所以先把给一下，用一个来做映射。还有的方法，参考 315. Count of Smaller Numbers After Self 题目链接：https://leetcode.com/problems... divi...

cnio 2019-08-14 17:34 评论0 收藏0
[LeetCode] 4Sum & 4Sum II

摘要：和方法一样，多一个数，故多一层循环。完全一致，不再赘述， 4Sum Problem Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which ...

sydMobile 2019-08-14 15:42 评论0 收藏0