# 【算法之美】你可能想不到的归并排序的神奇应用 — leetcode 327. Count of Range Sum

``/**  * @param {number[]} nums  * @param {number} lower  * @param {number} upper  * @return {number}  */ var countRangeSum = function(nums, lower, upper) {   var len = nums.length;    var ans = 0;    for (var i = 0; i < len; i++) {     var sum = 0;     for (var j = i; j < len; j++) {       sum += nums[j];       if (sum >= lower && sum <= upper)         ans++;     }   }    return ans; };``

``function binarySearch1(a, target) {   target += 1;   var start = 0     , end = a.length - 1;    while(start <= end) {     var mid = ~~((start + end) >> 1);     if (a[mid] >= target)       end = mid - 1;     else        start = mid + 1;   }    return start; }  function binarySearch2(a, target) {   var start = 0     , end = a.length - 1;    while(start <= end) {     var mid = ~~((start + end) >> 1);     if (a[mid] >= target)       end = mid - 1;     else        start = mid + 1;   }    return end; }   var countRangeSum = function(nums, lower, upper) {   var len = nums.length;    var sum = [];    var ans = 0;    var num = 0;    sum.push(0);    for (var i = 0; i < len; i++) {     ans += nums[i];      var a = ans - upper;     var b = ans - lower;      var pos1 = binarySearch2(sum, a) + 1;     var pos2 = binarySearch1(sum, b) - 1;      num += pos2 - pos1 + 1;      var pos3 = binarySearch1(sum, ans);      sum.splice(pos3, 0, ans);   }      return num;    };``

``// 返回 b[j] - a[i] 值在 [wlower, wupper] 范围内组数 function getAns(a, b) {    var sum = 0;    var lena = a.length;    var lenb = b.length;    var start = 0;   var end = 0;    for (var i = 0; i < lenb; i++) {      // to get start     while (b[i] - a[start] >= wlower) {       start++;     }      // to get end     while (b[i] - a[end] > wupper) {       end++;     }      sum += start - end;   }    return sum; }``

224ms！Your runtime beats 100.00% of javascriptsubmissions 还是有点小激动