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.
给出两个整数数组list 1和list 2，还有一个整数目标值，检查是否能在list 1里面找到一个数，在list 2里面找到一个数，两个数之和是目标值。返回是或者否。
1. 询问
是否可能有负数？是否会考虑溢出？对于空list的情况如何处理？
假设回答：可能有负数，不需考虑溢出，空list返回否。
2. 分析
暴力破解
这道题有一个很明显的暴力破解方法：尝试所有的list 1和list 2组合，当和为target的时候返回是，否则最后返回否。时间复杂度O(n^2)，空间复杂度O(1)。
为何低效？
因为没有空间的辅助来降低复杂度。比如说两个指针，p1指向list 1，p2指向list 2，二重循环为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
