题目前提是一定存在这样两个数
解法一就不写了…一般想不到吧
一开始想到的是解法二最后的用hash表
（其实是想到创建一个跟target一样大的数组啦..存在就写入index，但是要全部找出，那得二维数组，但是后面想到target要是很大的话，是不是浪费空间了…所以改成Dict）
后面发现题目只要求给出两个数就好了啊- –
扩展问题比较有意思
找三个应该不难，其它还不清楚，有想再补充…
1.二维数组
|
1
2
3
4
5
6
7
8
9
10
11
12
|
def find_pair(A, target): B= [[]for iin range(target+ 1)] for iin range(0,len(A)): if A[i] <= target: B[A[i]].append(i) for iin range(0, target/ 2 + 1): if len(B[i]) != 0 and len(B[target- i]) != 0: print(i, B[i], target-i, B[target-i]) if __name__== "__main__": A= [0,1,1,2,11,8,3,4,5,6,7,8,9,10] find_pair(A,9) |
2.字典
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
def find_pair(A, target): B= {} for iin range(0,len(A)): if A[i] <= target: if not B.has_key(A[i]): B[A[i]]= [i] else: B[A[i]].append(i) for iin range(0, target/ 2 + 1): if B.has_key(i)and B.has_key(target-i): print(i, B[i], target-i, B[target-i]) if __name__== "__main__": A= [0,1,1,2,11,8,3,4,5,6,7,8,9,10] find_pair(A,9) |
3.这种方法都已经重新排序了，不知道书上还返回索引有什么意义…排序偷懒直接用内置的啦…
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
def find_pair(A, target): A.sort() i, j= 0,len(A)- 1 while i < j: s= A[i]+ A[j] if s== target: print(i, A[i], j, A[j]) i+= 1 j-= 1 elif s < target: i+= 1 else: j-= 1 if __name__== "__main__": A= [0,1,1,2,11,8,3,4,5,6,7,8,9,10] find_pair(A,9) |
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
暂无评论内容