題意
給定一個包含 n 個整數(shù)的數(shù)組 nums 和一個目標(biāo)值 target锋恬，判斷 nums 中是否存在四個元素 a也物，b痢畜，c 和 d ，使得 a + b + c + d 的值與 target 相等锤灿？找出所有滿足條件且不重復(fù)的四元組。
注意點
- 如何使得結(jié)果不重復(fù)辆脸？
- 如何以
的復(fù)雜度求解但校？
解答
??假設(shè)滿足等式的下標(biāo)分別為1st，2st啡氢，3st状囱，4st，且依次遞增倘是。我們先用二重循環(huán)遍歷所有可取的1st和2st亭枷，再判斷是否存在對應(yīng)的3st和4st滿足：為避免超時，必須在常數(shù)時間內(nèi)完成尋找3st和4st搀崭。
叨粘，以
為鍵，數(shù)組
為值瘤睹，建立哈希表升敲。于是，對于給定的 1st 和 2st轰传，若哈希表中存在對應(yīng)鍵驴党，從鍵值中找到符合要求的[a,b]，
即為一個解获茬。
??執(zhí)行以上步驟前港庄，還需先將nums排序，便于避免重復(fù)的元素被遍歷恕曲。
Python代碼
class Solution:
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
hash1 = dict()
nums = sorted(nums)
add2 = [[-1] * len(nums) for i in range(len(nums))]
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
add2[i][j] = nums[i] + nums[j]
hash1[add2[i][j]] = []
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
hash1[add2[i][j]].append([i, j])
res = []
pre_f = None
for first in range(len(nums) - 3):
if nums[first] == pre_f:
continue
pre_f = nums[first]
pre_s = None
for second in range(first + 1, len(nums) - 2):
if nums[second] == pre_s:
continue
pre_s = nums[second]
t = target - nums[first] - nums[second]
if t not in hash1:
continue
candidate = hash1[t]
pre_t = None
for item in candidate:
if item[0] <= second or nums[item[0]] == pre_t:
continue
pre_t = nums[item[0]]
res.append([nums[first], nums[second], nums[item[0]], nums[item[1]]])
return res
