题目描述:

请设计一个高效算法,找出数组中两数之和为指定值的所有整数对。

给定一个int数组A和数组大小n以及需查找的和tsum,请返回和为tsum的整数对的个数。保证数组大小小于等于3000。

测试样例: [1,2,3,4,5],5,6

返回:2

思路一

直接用两层循环,将数组A中的所有数两两相加,每次相加得到的和与给定需要查找的和tsum比较,若相等,则计数器count+1,循环结束后返回计数器count

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
A = [1,2,3,4,5]
n = 5
tsum = 6
class FindPair:
def countPairs(self, A, n, tsum):
count = 0
i = 0
while i<n-1:
j = i + 1
while j<n:
if A[i] + A[j] == tsum:
count += 1
j += 1
i += 1
return count
test = FindPair()
test.countPairs(A,n,tsum)

思路二

先将数组按从小到大排序,再设两个指针,一个指针first指向数组第一个数字,另一个指针last指向数组最后一个数字,将首尾两个数字相加,得到和temp,此时会有一下几种情况:

  • temp < tsum 将较小的first往后移动 first = first_next
  • temp > tsum 将较大的last往前移动 last = last_prev
  • temp == tsum
    • 判断首尾两个数字是否相同,如果相同,说明这段数组中的所有数字都是相同的(3 3 3 3 3),
      所有的组合为:((last-first)*(last-first+1)) / 2
    • 判断首部是否有连续相同数字,如果有(2 2 2 3 4),则将首部后移直到与后一个不同为止,
      所有组合为:(first_next - first)*last
    • 判断尾部是否有连续相同数字,如果有(2 3 4 4 4),则将尾部前移直到与前一个不同为止,
      所有组合为:(last - last_prev)*first
    • 首尾都没有连续相同数字,则首部向后,尾部向前,继续相加判断
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
A = [1,2,3,4,5]
n = 5
tsum = 6
class FindPair:
def countPairs(self, A, n, tsum):
# 先对数组排序
A.sort()
count, first, last = 0, 0, n-1
while first < last:
temp = A[first] + A[last]
if temp == tsum:
if A[first] == A[last]:
# 3 3 3 3 3
count += ((last-first)*(last-first+1))>>1
break
else:
# 2 2 3 4 4
first_next = first + 1
while first_next <= last and A[first_next] == A[first]:
# 2 2 2 3 4
first_next += 1
last_prev = last - 1
while last_prev >= first and A[last_prev] == A[last]:
# 2 3 4 4 4
last_prev -= 1
count += (first_next - first)*(last - last_prev)
first = first_next
last = last_prev
elif temp < tsum:
first += 1
else:
last -= 1
return count
test = FindPair()
test.countPairs(A,n,tsum)

思路三

假设在数组A中有任意两个数a,b, 且有 a + b = tsum,那么必有tsum - b = a,且 a 在数组A中。

根据以上的结论,可以构造一个字典,把数组A中的所有数依次设为字典的每个键key,每个键的值设为1,然后循环遍历一次数组A,利用给定的需要查找的和值tsum - A中的值,验证得到的差值是否在字典中,如果在则说明符合题目要求,计数器count+1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
A = [1,2,3,4,5]
n = 5
tsum = 6
class FindPair:
def countPairs(self, A, n, tsum):
count = 0
map = {}
for a in A:
if tsum-a in map:
count += map [tsum-a]
map[a] = map.get(a,0)+1
return count
test = FindPair()
test.countPairs(A,n,tsum)

第13行用到了Python中字典的get()方法,它的语法是:dict.get(key, default=None)

key是字典中要查找的键, default指定键的值,该语句会返回指定键的值,如果指定键的值不存在时,返回该默认值值。

map.get(a,0)+1将数组A中的每个数(a)都设为键,且初始值是0,然后将为了计数数组中的每个数(a)的值加1

为什么不直接map.get(a,1)设为1呢?如果数组中有大量重复的数字(比如A[2,2,2,2,2…]),map.get(a,1)会把重复的数字的值都设为1(比如2:1,2:1,2:1,2:1,2:1),而map.get(a,0)+1会把重复的累积+1(比如2:5),这样count计数的时候累加的值是5,而不是1。