国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

leetcode327. Count of Range Sum

miya / 2114人閱讀

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

題目要求 
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.

這道題目是指，現(xiàn)有一個(gè)整數(shù)數(shù)組，并輸入上界值upper和下界值lower，問數(shù)組中一共有多少組連續(xù)的子數(shù)組，其子數(shù)組中數(shù)字的和在上界和下界之內(nèi)。

思路一：暴力循環(huán)

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

    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;
    }
思路二：分治法

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

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

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/74188.html

相關(guān)文章

  • 327. Count of Range Sum

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

    mj 評(píng)論0 收藏0

  • [LeetCode] 4Sum & 4Sum II

    摘要：和方法一樣，多一個(gè)數(shù)，故多一層循環(huán)。完全一致，不再贅述， 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 評(píng)論0 收藏0

  • 315. Count of Smaller Numbers After Self

    摘要：題目鏈接的題，用來做，這種求有多少的題一般都是。里多加一個(gè)信息表示以為的節(jié)點(diǎn)數(shù)。也可以做，因?yàn)槭墙y(tǒng)計(jì)有多少的，其實(shí)就是求從最小值到的。的是，要做一個(gè)映射，把的值映射到之間。所以先把給一下，用一個(gè)來做映射。還有的方法，參考 315. Count of Smaller Numbers After Self 題目鏈接：https://leetcode.com/problems... divi...

    cnio 評(píng)論0 收藏0

  • leetcode 部分解答索引（持續(xù)更新～）

    摘要：前言從開始寫相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒有按順序?qū)懍F(xiàn)在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個(gè)索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新 前言 從開始寫leetcode相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒有按順序?qū)憽F(xiàn)在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個(gè)索引嘻嘻。 順序整理 1~50 1...

    leo108 評(píng)論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...

    張金寶 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

miya

男|高級(jí)講師

TA的文章

閱讀更多
最新活動(dòng)
閱讀需要支付1元查看
<