LeetCode 327. 区间和的个数

我会带着你远行 2022-10-29 03:13 164阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]

//解法一：分治 68%
    class Solution {
        
        public int countRangeSum(int[] nums, int lower, int upper) {
        
            int n = nums.length;
            long[] sum = new long[n + 1];
            for(int i = 1; i <= n; i++){
        
                sum[i] = sum[i - 1] + nums[i - 1]; 
            }
            return countRangeSumRecursive(sum, lower, upper, 0, sum.length - 1);
        }
    
        public int countRangeSumRecursive(long[] sum, int lower, int upper, int left, int right){
        
            if(left == right)
                return 0;
            int mid = left + right >> 1;
            int n1 = countRangeSumRecursive(sum, lower, upper, left, mid);
            int n2 = countRangeSumRecursive(sum, lower, upper, mid + 1, right);
            int ret = n1 + n2;
            int i = left;
            int l = mid + 1, r = mid + 1;
            while(i <= mid){
        
                while(l <= right && sum[l] - sum[i] < lower) l++;
                while(r <= right && sum[r] - sum[i] <= upper) r++;
                ret += (r - l);
                i++;
            }
            int p = 0;
            int p1 = left, p2 = mid + 1;
            long[] sorted = new long[right - left + 1];
            while(p1 <= mid || p2 <= right){
        
                if(p1 > mid){
        
                    sorted[p++] = sum[p2++];
                }else if(p2 > right){
        
                    sorted[p++] = sum[p1++];
                }else{
        
                    if (sum[p1] < sum[p2]) {
        
                            sorted[p++] = sum[p1++];
                        } else {
        
                            sorted[p++] = sum[p2++];
                        }
                }
            }
            for (int k = 0; k < sorted.length; k++) {
        
                    sum[left + k] = sorted[k];
                }
            return ret;
        }
    }

//解法二：树状数组
    class Solution {
        
        public int countRangeSum(int[] nums, int lower, int upper) {
        
            long sum = 0;
            long[] preSum = new long[nums.length + 1];
            for(int i = 0; i < nums.length; i++){
        
                sum += nums[i];
                preSum[i + 1] = sum;
            }
    
            Set<Long> allNumbers = new TreeSet<Long>();
            for(long x : preSum){
        
                allNumbers.add(x - lower);
                allNumbers.add(x - upper);
                allNumbers.add(x);
            }
    
            Map<Long, Integer> values = new HashMap<Long, Integer>();
            int idx = 1;
            for(long x : allNumbers){
        
                values.put(x, idx);
                idx++;
            }
            int ret = 0;
            BIT bit = new BIT(values.size() + 1);
            for(int i = 0; i < preSum.length; i++){
        
                int left = values.get(preSum[i] - upper), right = values.get(preSum[i] - lower);
                ret += bit.query(right) - bit.query(left - 1);
                bit.update(values.get(preSum[i]), 1);
            }
            return ret;
        }
    }
    
    class BIT {
        
        int[] tree;
        int n;
    
        public BIT(int n) {
        
            this.n = n;
            this.tree = new int[n + 1];
        }
    
        public static int lowbit(int x) {
        
            return x & (-x);
        }
    
        public void update(int x, int d) {
        
            while (x <= n) {
        
                tree[x] += d;
                x += lowbit(x);
            }
        }
    
        public int query(int x) {
        
            int ans = 0;
            while (x != 0) {
        
                ans += tree[x];
                x -= lowbit(x);
            }
            return ans;
        }
    }

//解法三：线段树
    class Solution {
        
        public int countRangeSum(int[] nums, int lower, int upper) {
        
            long sum = 0;
            long[] preSum = new long[nums.length + 1];
            for (int i = 0; i < nums.length; ++i) {
        
                sum += nums[i];
                preSum[i + 1] = sum;
            }
            
            Set<Long> allNumbers = new TreeSet<Long>();
            for (long x : preSum) {
        
                allNumbers.add(x);
                allNumbers.add(x - lower);
                allNumbers.add(x - upper);
            }
            // 利用哈希表进行离散化
            Map<Long, Integer> values = new HashMap<Long, Integer>();
            int idx = 0;
            for (long x : allNumbers) {
        
                values.put(x, idx);
                idx++;
            }
            int[] a = new int[values.size()];
            TreeNode root = buildTree(a, 0, values.size() - 1);
            int ret = 0;
            for (long x : preSum) {
        
                int left = values.get(x - upper), right = values.get(x - lower);
                ret += queryTree(root, left, right);
                updateTree(root, values.get(x), 1);
            }
            return ret;
        }
    
        class TreeNode {
        
            int val;
            int start;
            int end;
            TreeNode left;
            TreeNode right;
    
            public TreeNode(int start, int end) {
        
                left = null;
                right = null;
                this.start = start;
                this.end = end;
            }
        }
    
        private TreeNode buildTree(int[] nums, int start, int end) {
        
            if (start > end) return null;
            TreeNode curr = new TreeNode(start, end);
            if (start == end) curr.val = nums[start];
            else {
        
                int mid = start + (end - start) / 2;
                curr.left = buildTree(nums, start, mid);
                curr.right = buildTree(nums, mid + 1, end);
                curr.val = curr.left.val + curr.right.val;
            }
            return curr;
        }
    
        public void updateTree(TreeNode node, int i, int val) {
        
            if (node.start == node.end) {
        
                node.val += val;
            } else {
        
                int mid = node.start + (node.end - node.start) / 2;
                if (i <= mid) updateTree(node.left, i, val);
                else updateTree(node.right, i, val);
                node.val = node.left.val + node.right.val;
            }
        }
    
        public int queryTree(TreeNode node, int i, int j) {
        
        	if(i > j)
        		return 0;
            if (node.start == i && node.end == j) return node.val;
            else {
        
                int mid = node.start + (node.end - node.start) / 2;
                if (j <= mid) {
        
                    return queryTree(node.left, i, j);
                } else if (i >= (mid + 1)) {
        
                    return queryTree(node.right, i, j);
                } else {
        
                    return queryTree(node.left, i, mid) + queryTree(node.right, mid + 1, j);
                }
            }
        }
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]: /images/20221024/56362082278c4c969ee1d0d56a4d58c5.png