给定一个整数数组，找到数组中所有有序元素对的数量，其和在给定范围[a,b]内。
以下是同样问题的O(n^2)解决方案。
'''
counts all pairs in array such that the
sum of pair lies in the range a and b
'''
def countpairs(array, a, b):
num_of_pairs = 0
for i in range(len(array)):
for j in range(i+1,len(array)):
total = array[i] + array[j]
if total >= a and total <= b:
num_of_pairs += 1
return num_of_pairs
我知道我的解决方案不是最优的，你有更好的算法吗？
时间复杂度显然与输出数量有关，但仍然优于现有算法：
O(nlogn) + O(k)
其中 k 是满足条件的配对数。
注意：如果你只需要计算配对数，那么可以在 O(nlogn) 的时间复杂度内完成。修改上述算法，使其也搜索小于 [b - x]（或下一个更小的元素）。这样，你就可以通过第一次和最后一次匹配的索引来简单地计算每个元素具有的“匹配”数量，时间复杂度为 O(logn)。然后只需将它们相加即可获得最终计数。这样，初始的 O(nlogn) 排序步骤就是主导因素。
首先对数组进行排序，然后通过两个索引计数对。这种基于两个索引的方法类似于2-sum问题中的方法，避免了二分查找需要进行N次的情况。算法的时间复杂度为排序复杂度 + O(N)，通常排序的复杂度为O(NlnN)，因此这种方法的时间复杂度为O(NlnN)。该算法的思想是，对于一个索引i，寻找一个下限和一个上限，使得a <= arr[i]+arr[low] <= arr[i]+arr[high] <= b，当i增大时，我们需要减小low和high来保持这个条件。为了避免重复统计同一对数，我们保证low > i，同时保持low <= high。以下计数方法的复杂度为O(N)，因为在while loop中，我们可以进行++i或--low或--high操作，最多有N次这样的操作。
//count pair whose sum is in [a, b]
//arr is a sorted array with size integers.
int countPair(int arr[], int size, int a, int b) {
int cnt = 0;
int i = 0, low = size-1, high = size－1;
while (i < high) {
//find the lower bound such that arr[i] + arr[low] < a,
//meanwhile arr[i]+arr[low+1] >= a
low = max(i, low);
while (low > i && arr[i] + arr[low] >= a) --low;
//find an upper bound such that arr[i] + arr[high] <= b
//meanwhile, arr[i]+arr[high+1] > b
while (high > low && arr[i] + arr[high] > b) --high;
//all pairs: arr[i]+arr[low+1], arr[i]+arr[low+2],...,arr[i]+arr[high]
//are in the rage[a, b], and we count it as follows.
cnt += (high-low);
++i;
}
return cnt;
}
st的初始值并不是在每次外部循环中从零或i开始，而是在每次迭代中递增。如果在第一次迭代中找到了end（例如通过二分查找），并且在内部循环中递增，则情况可能会更好... - greybearda = 6
array = [-20, 1, 3, 4, 8, 11]
output = [6, 4, 2, 2, 1, 1]
i, j = 0, 5
while i - j <= 0:
if array[i] + array[j] >= a:
output[j] = i
j -= 1
else:
output[i] = j + 1
i += 1
想象一下两个指针从两端开始向内移动，这是O(N)的。现在你只需要将条件改为b <= a，就可以做同样的事情了：
while i-j <= 0:
if array[i] + array[j] <= b:
output2[i] = j
i += 1
else:
output2[j] = i-1
j-=1
b = 9
array = [-20, 1, 3, 4, 8, 11]
output2 = [5, 4, 3, 3, 1, 0]
answer = [o2 - o + 1 - (o <= i <= o2) for i, (o, o2) in enumerate(zip(output, output2))]
这将产生：
answer = [0, 1, 1, 1, 1, 0]
这个和为4，对应于(1,8), (3,4), (4,3), (8, 1)
无论如何，正如你所看到的，这是sort + O(N)，这是最优的。
编辑：要求提供完整实现。已提供。供参考，完整代码：
def count_ranged_pairs(x, a, b):
x.sort()
output = [0] * len(x)
output2 = [0] * len(x)
i, j = 0, len(x)-1
while i - j <= 0:
if x[i] + x[j] >= a:
output[j] = i
j -= 1
else:
output[i] = j + 1
i += 1
i, j = 0, len(x) - 1
while i-j <= 0:
if x[i] + x[j] <= b:
output2[i] = j
i += 1
else:
output2[j] = i-1
j -=1
answer = [o2 - o + 1 - (o <= i <= o2) for i, (o, o2) in enumerate(zip(output, output2))]
return sum(answer)/2
i - j <= 1 的逻辑吗？为什么允许前向指针 i 超过后向指针 j 1 个单位？ - Ericfrom itertools import ifilter, combinations
def countpairs2(array, a, b):
pairInRange = lambda x: sum(x) >= a and sum(x) <= b
filtered = ifilter(pairInRange, combinations(array, 2))
return sum([2 for x in filtered])
return len(list(filtered)) * 2。这可能会更快，但代价是使用更多的RAM。在一些数据的限制下，我们可以在线性时间内解决问题（抱歉使用Java，我对Python不是很熟练）：
public class Program {
public static void main(String[] args) {
test(new int[]{-2, -1, 0, 1, 3, -3}, -1, 2);
test(new int[]{100,200,300}, 300, 300);
test(new int[]{100}, 1, 1000);
test(new int[]{-1, 0, 0, 0, 1, 1, 1000}, -1, 2);
}
public static int countPairs(int[] input, int a, int b) {
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int el : input) {
max = Math.max(max, el);
min = Math.min(min, el);
}
int d = max - min + 1; // "Diameter" of the array
// Build naive hash-map of input: Map all elements to range [0; d]
int[] lookup = new int[d];
for (int el : input) {
lookup[el - min]++;
}
// a and b also needs to be adjusted
int a1 = a - min;
int b1 = b - min;
int[] counts = lookup; // Just rename
// i-th element contain count of lookup elements in range [0; i]
for (int i = 1; i < counts.length; ++i) {
counts[i] += counts[i - 1];
}
int res = 0;
for (int el : input) {
int lo = a1 - el; // el2 >= lo
int hi = b1 - el; // el2 <= hi
lo = Math.max(lo, 0);
hi = Math.min(hi, d - 1);
if (lo <= hi) {
res += counts[hi];
if (lo > 0) {
res -= counts[lo - 1];
}
}
// Exclude pair with same element
if (a <= 2*el && 2*el <= b) {
--res;
}
}
// Calculated pairs are ordered, divide by 2
return res / 2;
}
public static int naive(int[] ar, int a, int b) {
int res = 0;
for (int i = 0; i < ar.length; ++i) {
for (int j = i + 1; j < ar.length; ++j) {
int sum = ar[i] + ar[j];
if (a <= sum && sum <= b) {
++res;
}
}
}
return res;
}
private static void test(int[] input, int a, int b) {
int naiveSol = naive(input, a, b);
int optimizedSol = countPairs(input, a, b);
if (naiveSol != optimizedSol) {
System.out.println("Problem!!!");
}
}
}
if (a <= 2*el && 2*el <= b)是必需的，因为算法总是计算成对(a[i], a[i])
- 算法需要额外的O(d)内存，这可能很多。我有一个解决方案（实际上有两个;-)）。用Python编写：
def find_count(input_list, min, max):
count = 0
range_diff = max - min
for i in range(len(input_list)):
if input_list[i]*2 >= min and input_list[i]*2 <= max:
count += 1
for j in range(i+1, len(input_list)):
input_sum = input_list[i] + input_list[j]
if input_sum >= min and input_sum <= max:
count += 2
类似于这样：
# list_maximum is the maximum number of the list (i.e) max(input_list), if already known
def find_count(input_list, min, max, list_maximum):
count = 0
range_diff = max - min
for i in range(len(input_list)):
if input_list[i] > max or input_list[i] + list_maximum < min:
continue
if input_list[i]*2 >= min and input_list[i]*2 <= max:
count += 1
for j in range(i+1, len(input_list)):
input_sum = input_list[i] + input_list[j]
if input_sum >= min and input_sum <= max:
count += 2
如果我发现更好的解决方案，我也会很高兴学习它 :-)。如果我找到了，我会更新这个答案。
我认为这是一个简单的数学问题，可以使用numpy解决，无需循环和排序。我不确定，但我认为复杂度在最坏情况下为O(N^2)（希望有更熟悉numpy时间复杂度的人确认一下）。
无论如何，这是我的解决方案：
import numpy as np
def count_pairs(input_array, min, max):
A = np.array(input_array)
A_ones = np.ones((len(A),len(A)))
A_matrix = A*A_ones
result = np.transpose(A_matrix) + A_matrix
result = np.triu(result,0)
np.fill_diagonal(result,0)
count = ((result > min) & (result < max)).sum()
return count
A = np.array(input_array)
A_ones = np.ones((len(A),len(A)))
A_matrix = A*A_ones
[1,1,2,2,3,-1]，因此，在这一点上，A_matrix 的值应该是这样的。[[ 1. 1. 2. 2. 3. -1.]
[ 1. 1. 2. 2. 3. -1.]
[ 1. 1. 2. 2. 3. -1.]
[ 1. 1. 2. 2. 3. -1.]
[ 1. 1. 2. 2. 3. -1.]
[ 1. 1. 2. 2. 3. -1.]]
result = np.transpose(A_matrix) + A_matrix
[[ 2. 2. 3. 3. 4. 0.]
[ 2. 2. 3. 3. 4. 0.]
[ 3. 3. 4. 4. 5. 1.]
[ 3. 3. 4. 4. 5. 1.]
[ 4. 4. 5. 5. 6. 2.]
[ 0. 0. 1. 1. 2. -2.]]
result = np.triu(result,0)
np.fill_diagonal(result,0)
Our result now looks like:
[[ 0. 2. 3. 3. 4. 0.]
[ 0. 0. 3. 3. 4. 0.]
[ 0. 0. 0. 4. 5. 1.]
[ 0. 0. 0. 0. 5. 1.]
[ 0. 0. 0. 0. 0. 2.]
[ 0. 0. 0. 0. 0. 0.]]
count = ((result > min) & (result < max)).sum()
如果可接受的域中包含0，则此方法将无法使用，但我相信将上述结果矩阵中的这些0转换为其他无意义的数字将是微不足道的....
A_ones = np.ones((len(A),len(A)))
A_matrix = A*A_ones
result = np.transpose(A_matrix) + A_matrix替换为：result = A + A[:,np.newaxis] - Eric>=a 和 <=b。即使进行了这个更正，count = ((result >= _min) & (result <= _max)).sum()，你的函数返回的结果比使用arr = [random.randint(-10, 10) for _ in xrange(1000)]; a = 6; b = 16的 OP 的函数少一个。 - wwiidef get_numOfPairs(array, start, stop):
num_of_pairs = 0
array_length = len(array)
for i in range(array_length):
for j in range(i+1, array_length):
if sum([array[i], array[j]]) in range(start, stop):
num_of_pairs += 1
return num_of_pairs
n = int(input())
ar = list(map(int, input().rstrip().split()))[:n]
count=0
uniq=[]
for i in range(n):
if ar[i] not in uniq:
uniq.append(ar[i])
for j in uniq:
if ((ar.count(j))%2==0):
count=count+((ar.count(j))/2)
if ((ar.count(j))%2!=0) & (((ar.count(j))-1)%2==0):
count=count+((ar.count(j)-1)/2)
print(int(count))
for j in range(i+1, len(array)):（这也意味着你不需要if i != j） - jcfollower