前往
大廳
主題

LeetCode - 454. 4Sum II 解題心得

Not In My Back Yard | 2022-09-11 12:00:17 | 巴幣 0 | 人氣 131

題目連結:


題目意譯:
給定四個整數陣列 nums1 、 nums2 、 nums3 以及 nums4,每個的長度皆為 n,回傳四元數組 (i, j, k, l) 之數量,其中每個數組滿足:
0 ≦ i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

限制:
n == nums1.length
n == nums2.length
n == nums3.length
n == nums4.length
1 ≦ n ≦ 200
-2 ^ 28 ≦ nums1[i], nums2[i], nums3[i], nums4[i] ≦ 2 ^ 28



範例測資:
範例 1:
輸入: nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
輸出: 2
解釋:
兩個四元數組為
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

範例 2:
輸入: nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
輸出: 1


解題思維:
可以看到直接窮舉是 O(n ^ 4)。

不過我們可以先窮舉 nums1 、 nums2 的所有可能數組(也就是 n ^ 2 個)然後把它們的數值丟雜湊表(Hash Table)裡以供查詢。接著,我們再窮舉 nums3 、 nums4 的所有數組然後到雜湊表看有無對應的「負值」(例如現在總和是 7,則代表我們要去雜湊表看有無 -7 存在),如果有就把所求加上其於雜湊表中出現數量(對應前一輪窮舉等於該值的數對數量)。

如此,窮舉完之後便可以得知所求。而其時間複雜度為兩次窮舉的時間也就是 O(n ^ 2) + O(n ^ 2) = O(n ^ 2)。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作