本文共 790 字，大约阅读时间需要 2 分钟。
问题A：
逆序数对个数：见：
问题B：
有序数组上和为指定值的二元数字对数量：窗口缩小，时间O(N)
初始L=0,R=n-1
若Arr[L] + Arr[R] > k ，则R– 若Arr[L] + Arr[R] < k ，则L++ 若Arr[L] + Arr[R] == k , 找到一对儿，L++,R–,若L或R位置上与之前数字相同则皆可与之前数字组成一对儿。问题C：
有序数组上和为指定值对三元数字对数量：遍历数组，作为第一个数字，找后面组成sum - Arr[i]的二元对儿。
时间O(N*N)问题D：
环形山峰中，互相可见山峰对儿数量：山峰高度都不同，数学题，2n-3对儿
基本原则，小找大。 除去最高峰和次高峰，剩下每座山峰有且只有2对儿，即2*(n-2)个。 证明如下，分两种情况，1，2，3，则1，2是一对儿，但1，3不是一对儿。 2，1，3，则2，3是一对儿，且3之后的山再高或再低都不可能与2成对儿。 次高峰和最高峰是一对儿，即1个。 总结，2n-3对儿。山峰高度可能相同，单调栈，时间O(N)
从任意一处最高点出发，单调栈维护高度递减，结构为（高度，数量），相同高度合并数量。 弹出时计算对儿数，若数量为1，则增加2个，否则增加2n+C(2,n)个。 注，在最后清算栈时，需要考虑倒数第二个记录是否为次高峰，即最后一个记录是否数量为1。问题E：
数组异或和为0的子数组的最多划分：哈希+dp，时间O(N)
维护一个一维dp表，表示Arr[0…i]的最多划分，
维护哈希表，（异或和，最大位置） 通过记录当前所有异或和sum，和哈希表，来找到当前窗口异或和为0的位置，即Arr[k…i]异或和为0，通过哈希表找到位置k。 动态转移方程：dp[i] = max{dp[i-1] , dp[k-1] + 1} or dp[i] = dp[i-1];转载地址：http://jbwji.baihongyu.com/