[Swift]LeetCode327. 区间和的个数 | Count of Range Sum_app

概述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 numsbetween indices i and j (i ≤ j), inclu

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 numsbetween 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 =,lower =,upper =,Output: 3 Explanation: The three ranges are :,and their respective sums are: .[-2,5,-1]-22[0,0][2,2][0,2]-2,-1,2

给定一个整数数组 nums，返回区间和在 [lower,upper] 之间的个数，包含 lower 和 upper。
区间和 S(i,j) 表示在 nums 中，位置从 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。

说明:
最直观的算法复杂度是 O(n2) ，请在此基础上优化你的算法。

示例:

输入: nums =,输出: 3 解释: 3个区间分别是:,它们表示的和分别为: [-2,2]，-2,2。

140 ms

 1 class Solution { 2     func countRangeSum(_ nums: [Int],_ lower: Int,_ upper: Int) -> Int { 3         let count = nums.count 4         if count == 0 { 5             return 0 6         } 7         var sums = Array(repeating: 0,count: count+1) 8          9         for i in 1..<count+1 {10             sums[i] = sums[i-1] + nums[i-1]11         }12         13         let maxSum = sums.max()!14         15         func mergeSort(_ low : Int,_ high : Int) -> Int {16             if low == high {17                 return 018             }19             let mID = (low + high) >> 120             var res = mergeSort(low,mID) + mergeSort(mID+1,high)21             var x = low,y = low22             for i in mID+1..<high+1 {23                 while x <= mID && sums[i] - sums[x] >= lower {24                     x += 125                 }26                 while y<=mID && sums[i] - sums[y] > upper {27                     y += 128                 }29                 res += (x-y)30             }31             32             let sli = Array(sums[low..<high+1])33             34             var l = low,h = mID + 135             36             for i in low..<high+1 {37                 x = l <= mID ? sli[l - low] : maxSum38                 y = h <= high ? sli[h - low] : maxSum39                 40                 if x < y {41                     l += 142                 }else {43                     h += 144                 }45                 sums[i] = min(x,y)46             }47             48             return res49         }50         51         return mergeSort(0,count)52     }53 }