<strike id="u6igi"><input id="u6igi"></input></strike><ul id="u6igi"></ul>

leetcode327. Count of Range Sum

miya 發布于2019-08-16 16:47 / 2126人閱讀

摘要：接著計算所有子數組中元素的和，并判斷是否位于數值區間內。因此，在對左右子數組進行排序后，以左子數組中的每一位作為開頭，在右子數組中找到滿足和區間的第一個值，和超過區間的第一個值。則二者的差即為橫穿左右的滿足條件的子數組個數。

題目要求

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.

Note:
A naive algorithm of O(n2) is trivial. You MUST do better than that.

Example:

Input: nums = [-2,5,-1], lower = -2, upper = 2,
Output: 3 
Explanation: The three ranges are : [0,0], [2,2], [0,2] and their respective sums are: -2, -1, 2.

這道題目是指，現有一個整數數組，并輸入上界值upper和下界值lower，問數組中一共有多少組連續的子數組，其子數組中數字的和在上界和下界之內。

思路一：暴力循環

我們可以首先遍歷一遍數組，計算子數組下標[0,i）的所有元素的和。根據該結果可以計算自數組[i,j)中所有元素的和。接著計算所有子數組中元素的和，并判斷是否位于數值區間內。代碼如下：

    public int countRangeSum(int[] nums, int lower, int upper) {
        long[] sums = new long[nums.length+1];
        for(int i = 0 ; i= lower && sums[j] - sums[i] <= upper) {
                    count++;
                }
            }
        }
        return count;
    }

思路二：分治法

分治法的核心思路在于，將計算整個數組的符合條件的子數組的問題切分為子問題，將數組一分為二，并分別計算左子數組的符合條件的子數組個數，右子數組中符合條件的子數組個數和橫穿左右數組的符合條件的子數組個數。
計算橫穿左右的子數組個數的方法很有趣，這采用了歸并排序的思想，即無論左子數組中的元素或是右子數組中的元素如何變動，橫穿左右的子數組個數都不會受影響。因此，在對左右子數組進行排序后，以左子數組中的每一位作為開頭，在右子數組中找到滿足upper和lower區間的第一個值，和超過upper區間的第一個值。則二者的差即為橫穿左右的滿足條件的子數組個數。

    public int countRangeSum3(int[] nums, int lower, int upper) {
        long[] sums = new long[nums.length + 1];
        for(int i = 0 ; i

云服務器 GPU云服務器 Leetcod LeetCode range() Range

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/74188.html

327. Count of Range Sum

摘要：題目鏈接這題實際就是給定范圍內的，的方法。注意一開始把加進去，考慮結果是的情況，還有要用型，以免會還是可以來做，要統計范圍內的個數，就是用。 327. Count of Range Sum 題目鏈接：https://leetcode.com/problems... 這題實際就是給定范圍內的range sum，divide and conquer的方法。一路計算prefixSum[0:i...

mj 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
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 部分解答索引（持續更新～）

摘要：前言從開始寫相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫現在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言從開始寫leetcode相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫～現在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。順序整理 1~50 1...

leo108 2019-08-15 14:26 評論0 收藏0
[LeetCode] Path Sum (I & II & III)

摘要： 112. Path Sum Problem Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. Note: A leaf is a node...

張金寶 2019-08-19 11:09 評論0 收藏0