文章目錄

• • 1. 題目
  • 2. 解題
  • • 2.1 動態規劃超時
    • 2.2 二分查找
    • 2.3 歸并排序

1. 題目

給定一個整數數組 nums，返回區間和在 [lower, upper] 之間的個數，包含 lower 和 upper。

區間和 S(i, j) 表示在 nums 中，位置從 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。

說明:
最直觀的算法復雜度是 O(n2) ，請在此基礎上優化你的算法。

示例: 輸入: nums = [-2,5,-1], lower = -2, upper = 2, 輸出: 3 解釋: 3個區間分別是: [0,0], [2,2], [0,2]，它們表示的和分別為: -2, -1, 2。

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/count-of-range-sum
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

2.1 動態規劃超時

• 區間動態規劃，超時例子，復雜度太高 $O(n^2)$
• 整型溢出例子[2147483647,-2147483648,-1,0] -1 0
  

class Solution { public:int countRangeSum(vector<int>& nums, int lower, int upper) {if(nums.size() == 0)return 0;int i, j, len, n = nums.size(), count=0;vector<vector<long>> dp(n,vector<long>(n,0));//區間[i,j]的和for(i = 0; i < n; ++i){dp[i][i] = nums[i];if(lower<=dp[i][i] && dp[i][i]<=upper)count++;}for(len = 1; len < n; ++len){for(i = 0; i < n-len; ++i){dp[i][i+len] = dp[i][i+len-1] + dp[i+len][i+len];if(lower<=dp[i][i+len] && dp[i][i+len]<=upper)count++;}}return count;} };

2.2 二分查找

• 參考大佬的解法
• 前綴和 sum， $L\le sum[j]?sum[i]\le U?sum[j]?U\le sum[i]\le sum[j]?L$
• j = 0 時, 上式 sum[i] = 0，sum[i] 可以看做前面的和， sum[j] 當前的和
• 以每個 j 點作為結束的區間，前面哪些 i 到 j 的和在范圍內
• 將前次的前綴和插入multiset，有序，可以二分查找
• 查找set中前綴值在 當前 前綴和 $sum[j]$ 上下范圍內（$[sum[j]?U,sum[j]?L]$）的個數

class Solution { public:int countRangeSum(vector<int>& nums, int lower, int upper) {if(nums.size() == 0)return 0;multiset<long> s;s.insert(0);int count = 0;long sum = 0;for(int i = 0; i < nums.size(); ++i){sum += nums[i];count += distance(s.lower_bound(sum-upper), s.upper_bound(sum-lower));s.insert(sum);}return count;} };

但是上面解法中distance在set中（不可隨機訪問）是 O(n)時間復雜度的，所以用數組進行二分查找兩個端點，然后做差會更快些。
80 ms 14.4 MB

2.3 歸并排序

• 其實歸并排序求逆序度是本題的一個特例
• 對前綴和進行歸并排序（注意頭部要加一個0，用于第一個數的）
• 歸并時，固定左邊的一個端點，右邊有兩個指針進行遍歷查找

核心代碼段：

int i = l, jlo = mid+1, jup = mid+1;//右側兩個指針while(i <= mid)//遍歷左側的端點{ while(jlo <= r && sum[jlo]-sum[i] < lower)//[i,jlo]不在范圍內jlo++;while(jup <= r && sum[jup]-sum[i] <= upper)//[i,jup]在范圍內jup++;//最后 [jlo,jup) 為在范圍內的右端點count += jup-jlo;//計數i++;//遍歷下一個左端點} class Solution {vector<long> temp; public:int countRangeSum(vector<int>& nums, int lower, int upper) {if(nums.size() == 0)return 0;vector<long> sum(nums.size()+1, 0);temp.resize(nums.size()+1);for(int i = 1; i < sum.size(); ++i)sum[i] = sum[i-1] + nums[i-1];return mergeSort(sum,0,sum.size()-1,lower,upper);}int mergeSort(vector<long>& sum, int l, int r, int lower, int upper){if(l >= r)return 0;int mid = l+((r-l)>>1), count = 0;count += mergeSort(sum, l, mid, lower, upper);count += mergeSort(sum, mid+1, r, lower, upper);int i = l, jlo = mid+1, jup = mid+1;while(i <= mid){while(jlo <= r && sum[jlo]-sum[i] < lower)jlo++;while(jup <= r && sum[jup]-sum[i] <= upper)jup++;count += jup-jlo;i++;}//合并，跟歸并排序一致i = l; int j = mid+1, k = 0;while(i <= mid && j <= r){if(sum[i] <= sum[j])temp[k++] = sum[i++];elsetemp[k++] = sum[j++];}if(i <= mid)while(i <= mid)temp[k++] = sum[i++];elsewhile(j <= r)temp[k++] = sum[j++];for(i = 0; i < k; ++i)sum[l++] = temp[i];return count;} };

28 ms 12.2 MB

總結

以上是生活随笔為你收集整理的LeetCode 327. 区间和的个数（multiset二分查找/归并排序）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。