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è)回答：可能有負數(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