Given two integer arrays list 1 and list 2 and an int target value, check if there exists such a sum, where one number taken from list 1 and another taken from list 2 to add up to become the target value. Return true or false.
給出兩個整數(shù)數(shù)組list 1和list 2，還有一個整數(shù)目標值，檢查是否能在list 1里面找到一個數(shù)闲昭，在list 2里面找到一個數(shù)，兩個數(shù)之和是目標值自沧。返回是或者否。
1. 詢問
是否可能有負數(shù)树瞭？是否會考慮溢出拇厢？對于空list的情況如何處理？
假設回答：可能有負數(shù)晒喷，不需考慮溢出孝偎，空list返回否。
2. 分析
暴力破解
這道題有一個很明顯的暴力破解方法：嘗試所有的list 1和list 2組合凉敲，當和為target的時候返回是衣盾，否則最后返回否。時間復雜度O(n^2)爷抓，空間復雜度O(1)势决。
為何低效？
因為沒有空間的輔助來降低復雜度蓝撇。比如說兩個指針果复，p1指向list 1，p2指向list 2渤昌，二重循環(huán)為for p1 in list1 for p2 in list2虽抄，那么p2相當于要遍歷list 2多遍，這屬于不必要的重復独柑。
改進
在p2遍歷list 2的同時迈窟，把list 2的元素都放進一個hash map里面，之后對于p1忌栅，直接查找target - p1是不是在hash map里面即可车酣。時間復雜度O(n)，空間復雜度O(n)。
其他方法
對兩個list排序骇径，p1從list 1的index=0開始，p2從list 2的index=end開始者春，相加之后和target相比較破衔，假如大于target，則要想辦法減小钱烟，即p2--晰筛，小于則p1++，相等返回true拴袭，遍歷完成還沒有找到返回false读第。瓶頸是在排序上，時間復雜度O(nlogn)拥刻，空間復雜度O(1)怜瞒。
3. 代碼
# T:O(n) S:O(n)
class Solution:
def sumOfTwoLists(self, l1, l2, t):
if not l1 or not l2:
return False
d = {}
for i in l2:
d[i] = True
for i in l1:
if t - i in d:
return True
return False
if __name__ == "__main__":
print(Solution().sumOfTwoLists([], [1], 1))
print(Solution().sumOfTwoLists([1, 5, 3, 8], [4, 7, 3, 2, 9, 8], 10))
print(Solution().sumOfTwoLists([1, 5, 3, 8], [4, 7, 3, 2, 9, 8], 2))
難度
Easy
