给定一个int数组A及其大小n以及需查找的和sum,请返回数组中两数之和为sum的整数对的个数。保证数组大小小于等于3000。
测试样例:
[1,2,3,4,5],5,6
返回:2
class FindPair: def countPairs(self, A, n, tsum): # write code here d = {} res = 0 nres = 0 for i in A: if i not in d: d[i] = 1 else: d[i] += 1 for k, v in d.items(): if k != (tsum - k) and (tsum - k) in d: res += d[k] * d[tsum - k] if tsum % 2 == 0 and (tsum / 2) in d: nres = d[tsum / 2] * (d[tsum / 2] - 1) / 2 return res / 2 + nres
python O(n) solution
from collections import defaultdict
class FindPair:
def countPairs(self, A, n, tsum):
dd=defaultdict(int)
for i in A:dd[i]+=1
setA=list(set(A))
setA.sort()
start, end = 0, len(set(A))-1
res = 0
while start < end:
if setA[start] + setA[end] < tsum:
start += 1
elif setA[start] + setA[end] > tsum:
end -= 1
else:
res += dd[setA[start]]*dd[setA[end]]
start+=1
end-=1
if setA[start]*2==tsum:
res+=dd[setA[start]]*(dd[setA[start]]-1)//2
return res
# -*- coding:utf-8 -*- class FindPair: def countPairs(self, A, n, tsum): # write code here from collections import Counter if A == []: return 0 a, b, cnt = Counter(A), list(set(A)), 0 while len(b) != 0 : i = b[0] j = tsum - i if j in a and j != i: cnt += a[i] * a[j] del a[i], a[j] del b[b.index(i)] del b[b.index(j)] elif not j in a: del a[i] del b[b.index(i)] elif i == j: cnt += (a[i] * (a[i] - 1)) // 2 del a[i] del b[b.index(i)] return cnt
# -*- coding:utf-8 -*- class FindPair: def countPairs(self, A, n, tsum): if n < 2: return 0 A.sort() count = 0 i = 0 j = n - 1 while i < j: if A[i] + A[j] == tsum: if A[i] == A[j]: x = j - i + 1 count += (x*(x-1)/2) break else: samei = 1 samej = 1 while i < j and A[i] == A[i + 1]: samei += 1 i += 1 while i < j and A[j] == A[j - 1]: samej += 1 j -= 1 count += samei * samej i += 1 j -= 1 elif A[i] + A[j] > tsum: j -= 1 else: i += 1 return count