題意
給定一個包含 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