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

发布时间：2020-12-14 05:06:11 所属栏目：百科来源：网络整理

导读：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 algori

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 0
18             }
19             let mid = (low + high) >> 1
20             var res = mergeSort(low,mid) + mergeSort(mid+1,high)
21             var x = low,y = low
22             for i in mid+1..<high+1 {
23                 while x <= mid && sums[i] - sums[x] >= lower {
24                     x += 1
25                 }
26                 while y<=mid && sums[i] - sums[y] > upper {
27                     y += 1
28                 }
29                 res += (x-y)
30             }
31             
32             let sli = Array(sums[low..<high+1])
33             
34             var l = low,h = mid + 1
35             
36             for i in low..<high+1 {
37                 x = l <= mid ? sli[l - low] : maxSum
38                 y = h <= high ? sli[h - low] : maxSum
39                 
40                 if x < y {
41                     l += 1
42                 }else {
43                     h += 1
44                 }
45                 sums[i] = min(x,y)
46             }
47             
48             return res
49         }
50         
51         return mergeSort(0,count)
52     }
53 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!