題目前提是一定存在這樣兩個數
解法一就不寫了...一般想不到吧
一開始想到的是解法二最後的用hash表
(其實是想到創建一個跟target一樣大的數組啦..存在就寫入index,但是要全部找出,那得二維數組,但是後面想到target要是很大的話,是不是浪費空間了...所以改成Dict)
後面發現題目只要求給出兩個數就好了啊- -
擴展問題比較有意思
找三個應該不難,其它還不清楚,有想再補充...
1.二維數組
def find_pair(A, target): B = [[] for i in range(target + 1)] for i in range(0, len(A)): if A[i] <= target: B[A[i]].append(i) for i in 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.字典
def find_pair(A, target): B = {} for i in 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 i in 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.這種方法都已經重新排序了,不知道書上還返回索引有什麼意義...排序偷懶直接用內置的啦...
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)