本文共 3230 字，大约阅读时间需要 10 分钟。
分析: 这一题是让我们在一个数组中找一系列区间，区间中的数求和的结果在lower与upper之间，我们需要计算出这样的区间的个数。
解题：可以使用分治的思想来解这一题。首先，我们先计算出求和数组sum, 当需要计算区间[i,j]内的数的和时，只用求sum[j]-sum[i]就可以了。另外需要注意sum[0] = 0，这是为了计算区间[0,1]而保留的值。所以sum的总长度为size(nums)+1。
原问题可以转化为求左边半个数组的count，求右半边数组的count，以及跨两边数组的count。而主要的难点就是计算跨两边数组的区间的数量。我们可以遍历左半边的元素i，在右半边中找到j满足sum[j]-sum[i]位于lower和upper之间。如果右半边的sum值是有序的（为什么可以排序？两边分别排序后，右半边的元素仍然在右半边，左半边的元素仍然在左半边，我们排序的对象都是求和的值，他们的顺序并不重要，只要知道sum[j]-sum[i]时确保j在i的右边即可。），那么我们只要找到一个下界，找到一个上界，求出区域的大小，就能求出区间的个数了。因为对左半边也进行了排序，所以下界和上界可以重复使用，不需要重新计算。所以可以在分治的过程中同时进行归并排序，所有的跨两边的计算都是在两边都有序的情况下进行了。
ps：这里使用到的inplace_merge函数是<algorithm>头文件中的，可以帮我们省去归并排序中合并的操作，inplace_mege(a,b,c)中，a是左半边的头部，b是右半边的头部，c是右半边的尾部+1。
代码如下：
int merge(vector& sum, int lower, int upper, int left, int right) { if(left >= right) return 0; int mid = (left+right)/2; int x = mid+1, y = mid+1; int count = merge(sum, lower, upper, left, mid)+merge(sum, lower, upper, mid+1, right); for(int i = left; i <= mid; i++) { while(sum[x]-sum[i] < lower && x <= right) x++; while(sum[y]-sum[i] <= upper && y <= right) y++; count += y-x; } inplace_merge(sum.begin()+left, sum.begin()+mid+1, sum.begin()+right+1); return count;}int countRangeSum(vector & nums, int lower, int upper) { long t = 0; int size = nums.size(); if(size == 0) return 0; vector sum = {0}; for(int i = 0; i < size; i++) { t += nums[i]; sum.push_back(t); } return merge(sum, lower, upper, 0, size);}
分析：同样可以使用分治的思想来解题。对于两个有序数组，我们先调整，使得总有nums1的长度比nums2的长度要短。要找中位数，可以转化为找第K个数的问题(具体还要分奇偶判断，偶数再进行求和除2就行了)。具体算法如下：设两段数组分别为nums1,nums2,当前长度分别为len1, len2,对两段分别找到中间（二分）的nums1[mid1]与nums2[mid2]，如果nums1[mid1]大于nums2[mid2]（或者大于等于）时，
1.当num1的一半的长度加上num2的一半的长度已经超过第K个数了，那么我们可以丢弃掉nums1的后半段，因为他们不会影响到第K个数的判断
2.当num1的一半的长度加上num2的一半的长度未达到第K个数，那么我们可以取nums2的前半段（同时剔除），因为他们一定会在前K个数中出现。
以此逐渐缩小空间，nums1[mid1]小于nums2[mid2]（或者小于等于）的情况以此类推,因为涉及到头疼的+1,-1问题，需要计算清楚。
所以通过二分的方法我们就能达到时间复杂度O(log(m+n))
double findK(vector &nums1, vector &nums2, int s1, int len1, int s2, int len2, int K) { if(len1 <= 0) return nums2[s2+K-1]; if(len2 <= 0) return nums1[s1+K-1]; int mid1 = len1/2; int mid2 = len2/2; if(nums1[s1+mid1] >= nums2[s2+mid2]) { if(mid1+mid2+1 >= K) { // 丢弃nums1的后半段 return findK(nums1, nums2, s1, mid1, s2, len2, K); } else { // 纳入nums2的前半段 return findK(nums1, nums2, s1, len1, s2+mid2+1, len2-mid2-1, K-mid2-1); } } else { if(mid1+mid2+1 >= K) { // 丢弃nums2的后半段 return findK(nums1, nums2, s1, len1, s2, mid2, K); } else { // 纳入nums1的前半段 return findK(nums1, nums2, s1+mid1+1, len1-mid1-1, s2, len2, K-mid1-1); } }}double findMedianSortedArrays(vector & nums1, vector & nums2) { int len1 = nums1.size(), len2=nums2.size(); if(!len1 && !len2) // 两个数组都为空时 return 0; if( (len1+len2)%2 ) // 总长度为奇数 return findK(nums1, nums2, 0, len1, 0, len2, (len1+len2)/2 + 1); else { // 总长度为偶数 int a = findK(nums1, nums2, 0, len1, 0, len2, (len1+len2)/2 ); int b = findK(nums1, nums2, 0, len1, 0, len2, (len1+len2)/2 + 1 ); return (a+b)/2.0; } }
转载地址：http://iwwob.baihongyu.com/