leetcode327. 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.

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を入力し、配列の中に連続するサブ配列が何組あるかを尋ね、そのサブ配列の中で数字の和が上界と下界の中にある.
考え方1:暴力循環
まず配列を巡回し、サブ配列の下にある[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;
    }

考え方2:分治法
分治法の核心構想は,全配列の適合条件を計算するサブ配列の問題をサブ問題に切り分け,配列を二つに分け,左サブ配列の適合条件をそれぞれ計算するサブ配列個数,右サブ配列の適合条件を満たすサブ配列個数,左右サブ配列を横切る適合条件のサブ配列個数をそれぞれ計算することである.興味深いことに、これは、左サブ配列中の要素や右サブ配列中の要素がどのように変動しても、左右を横切るサブ配列の個数に影響を及ぼさないという帰結ソートの考え方を採用している.したがって、左右のサブ配列をソートした後、左サブ配列中の各ビットを先頭に、右サブ配列でupperとlower区間を満たす最初の値を見つけ、upperを超える区間の最初の値.両者の差は、左右を横切る条件を満たすサブ配列の個数である.

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