??算法，不如說(shuō)它是一種思考方式??
算法專(zhuān)欄： ????123
hash是什么，哈希表為什么叫哈希表？
一、??454. 四數(shù)相加 II
-
題目描述：給你四個(gè)整數(shù)數(shù)組
nums1、nums2、nums3和nums4，數(shù)組長(zhǎng)度都是n，請(qǐng)你計(jì)算有多少個(gè)元組(i, j, k, l)能滿足：0 <= i, j, k, l < nnums1[i] + nums2[j] + nums3[k] + nums4[l] == 0 - 來(lái)源：力扣（LeetCode）
- 難度：中等
- 提示：
n == nums1.lengthn == nums2.lengthn == nums3.lengthn == nums4.length1 <= 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
解釋?zhuān)簝蓚€(gè)元組如下：
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
??解題
哈希表
4個(gè)數(shù)組如果使用暴力解法就需要4層for循環(huán)，那時(shí)間復(fù)雜度將是O(n4)。
所以和上一題LeetCode：1. 兩數(shù)之和類(lèi)似，本題還是可以使用哈希表。我們可以把四個(gè)數(shù)組分為兩個(gè)組，分別對(duì)每個(gè)組求和（時(shí)間復(fù)雜度O(n2) ），將第一組求和結(jié)果加入到map的key中，value就是出現(xiàn)的次數(shù)。第二組就用于尋找map中是否有相反數(shù)，最后統(tǒng)計(jì)次數(shù)返回。
- code：
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
Map<Integer,Integer> map=new HashMap<>();
for (int i = 0; i < nums1.length; i++) {
for (int j = 0; j < nums2.length; j++) {
if(!map.containsKey(nums1[i]+nums2[j])){
map.put(nums1[i]+nums2[j],1);
}else{
map.put(nums1[i]+nums2[j],map.get(nums1[i]+nums2[j])+1 );
}
}
}
int ans=0;
for (int i = 0; i < nums3.length; i++) {
for (int j = 0; j < nums4.length; j++) {
if(map.containsKey(-(nums3[i]+nums4[j]))){
ans+=map.get(-(nums3[i]+nums4[j]));
}
}
}
return ans;
}
}
返回第一頁(yè)。?
?物有本末，事有終始，知所先后。??
文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-423626.html
???????我的CSDN???????? 文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-423626.html
到了這里，關(guān)于LeetCode：454. 四數(shù)相加 II —— 哈希表為什么叫哈希表~的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
