请你用python3写一下这道题，时间复杂度要求小于O(n^2)，给你一个下标从 0 开始、长度为 n 的整数数组 nums ，和两个整数 lower 和 upper ，返回 公平数对的数目 。 如果 (i, j) 数对满足以下情况，则认为它是一个 公平数对 ： 0 <= i < j < n，且 lower <= nums[i] + nums[j] <= upper

下面是一个符合要求的 python3 程序：

from collections import Counter

def countRangeSum(nums, lower, upper):
    presum = [0]
    for num in nums:
        presum.append(presum[-1] + num)

    res = 0
    c = Counter()
    for j in range(len(presum)):
        for i in range(j):
            if lower <= presum[j] - presum[i] <= upper:
                res += 1

        res += c[presum[j] - lower + 1] - c[presum[j] - upper]
        c[presum[j]] += 1

    return res

这个程序使用了前缀和和计数排序的思想，时间复杂度为 O(n log n)，符合要求。

相关问题

用Python设计一个时间复杂度为O（logn）的算法

以下是一个时间复杂度为O（logn）的例子：

二分查找算法

二分查找适用于有序序列中查找特定元素的情况。它的时间复杂度为O（logn）。

算法步骤：

1. 设置区间的首、尾指针low和high分别指向数字序列（或某种数据结构）中要查找的区间段。

2. 取中间位置mid，如果mid小于要查找的值，则将low指向mid+1；如果mid大于要查找的值，则将high指向mid-1；否则，mid就是要找的元素。

3. 重复这个过程，直到要查找的元素被找到或区间为空。

示例代码：

def binary_search(arr, low, high, x):

# 递归终止条件：当前区间为空
if high >= low:

mid = (high + low) // 2

# 如果中间元素是要查找的值，则返回它的下标
if arr[mid] == x:

return mid

# 如果中间元素比要查找的值大，则在左半边继续查找
elif arr[mid] > x:

return binary_search(arr, low, mid - 1, x)

# 反之，在右半边继续查找
else:

return binary_search(arr, mid + 1, high, x)

# 如果当前区间为空，则返回-1
else:

return -1

arr = [2, 3, 4, 10, 40]

x = 10

result = binary_search(arr, 0, len(arr)-1, x)

if result != -1:

print("元素在数组中的下标为 %d" % result)

else:

print("元素不在数组中")

创建一个顺序表，存放在数组 a[n]中，元素的类型为整型，设计算法调整 a，使其左边的所有元素小于 0，右边的所有元素大于 0（要求算法的时间复杂度和空 间复杂度均为 o(n)）。

### 回答1：
可以使用双指针法来实现该算法。具体步骤如下：

1. 定义两个指针 left 和 right，分别指向数组的第一个元素和最后一个元素。

2. 当 left 指向的元素小于 0 时，left 向右移动一位。

3. 当 right 指向的元素大于 0 时，right 向左移动一位。

4. 如果 left 和 right 指向的元素都不满足上述条件，则交换它们的值，并将 left 向右移动一位，right 向左移动一位。

5. 重复步骤 2-4，直到 left 和 right 相遇。

6. 此时，数组中所有小于 0 的元素都在 left 左边，所有大于 0 的元素都在 right 右边。

该算法的时间复杂度为 O(n)，空间复杂度为 O(1)。

### 回答2：
可以采用双指针算法来实现要求。

首先，我们定义两个指针left和right，分别指向数组的头部和尾部。

然后，不断进行如下操作：

1. 当a[left]小于0时，left指针右移一位；
2. 当a[right]大于0时，right指针左移一位；
3. 如果left指针仍然小于right指针，交换a[left]和a[right]的值；
4. 重复1-3步骤，直到left指针不小于right指针。

最终，当left指针不小于right指针时，所有左边元素都小于0，右边元素都大于0。

该算法的时间复杂度和空间复杂度均为O(n)，因为只需遍历一次数组即可完成调整。

以下是代码示例：

def adjust_array(a):
    left = 0
    right = len(a)-1

    while left < right:
        while a[left] < 0:
            left += 1
        while a[right] > 0:
            right -= 1

        if left < right:
            a[left], a[right] = a[right], a[left]

    return a

调用该函数，可以得到调整后的数组。

### 回答3：
算法思路：
将数组分为左右两部分，左边部分存放小于0的元素，右边部分存放大于0的元素。首先需要找到第一个大于0的元素的下标，然后将小于0的元素依次向前移动，并将大于0的元素放到数组的尾端。

算法步骤：
1. 初始化两个指针left和right，分别指向数组的第一个和最后一个元素。
2. 移动left指针，直到找到第一个大于等于0的元素。
3. 移动right指针，直到找到第一个小于0的元素。
4. 如果left < right，则交换left和right指向的元素，并分别将left和right指针向后、向前移动一位。
5. 重复步骤4，直到left >= right。
6. 此时，left左边的元素都小于0，right右边的元素都大于0。

时间复杂度和空间复杂度分析：
该算法只需要遍历一次数组，因此时间复杂度为O(n)。同时只使用了常数个辅助变量，因此空间复杂度也为O(1)。

代码实现：

void adjustArray(int a[], int n) {
    int left = 0;
    int right = n - 1;
    
    while (left < right) {
        while (left < right && a[left] < 0) {
            left++;
        }
        
        while (left < right && a[right] >= 0) {
            right--;
        }
        
        if (left < right) {
            int temp = a[left];
            a[left] = a[right];
            a[right] = temp;
            left++;
            right--;
        }
    }
}