給定四個(gè)包含整數(shù)的數(shù)組列表 A , B , C , D ,計(jì)算有多少個(gè)元組 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。
首先將四個(gè)數(shù)組分割為兩兩數(shù)組，前兩個(gè)數(shù)組值相加，后兩個(gè)數(shù)組相加，入股前兩個(gè)數(shù)組相加和與后兩個(gè)數(shù)組相加和正好為相反數(shù)，四個(gè)元素之和為0.
首先：
將兩數(shù)組的元素進(jìn)行遍歷相加，相加之和為map的索引。所指向的元素，就是出現(xiàn)的次數(shù)。
func foursumcount(A []int, B []int, C []int, D []int) int{
des :=map[int]int{}
for _,v:=range A{
for _,w:=range B{
des[v+w]++
}
}
}
再次遍歷另兩個(gè)數(shù)組，將兩個(gè)數(shù)組的元素進(jìn)行相加，取和的相反數(shù)，通過使用相反數(shù)在map中查找，如果沒出現(xiàn)，所指向的數(shù)是0，如果出現(xiàn)過這個(gè)數(shù)的相反數(shù)，則所指向的數(shù)大于一。
func foursumcount(A []int, B []int, C []int, D []int) int{
des :=map[int]int{}
ans:=0
for _,v:=range C{
for _,w:=range D{
ans +=des[-v-w]
}
}
}
最后將總數(shù)返回
全部代碼
func fourSumCount(A []int, B []int, C []int, D []int) int {
des := map[int]int{}
ans:=0
for _,v :=range A{//遍歷兩個(gè)數(shù)組，將兩個(gè)數(shù)組的和作為一個(gè)索引，進(jìn)行+1操作
for _,w:=range B{
des[v+w]++
}
}
for _,v :=range C{//遍歷另兩個(gè)數(shù)組，如果這兩個(gè)數(shù)組進(jìn)行相加的和的相反數(shù)在map中不為1,則證明出現(xiàn)過
for _,w:=range D{
ans +=des[-v-w]
}
}
return ans//返回總數(shù)
}
補(bǔ)充：算法題：三個(gè)數(shù)相加等于某個(gè)特定值
題目來自于leetcode第十五題
給定一個(gè)n個(gè)整數(shù)的數(shù)組S，是否存在S中的元素a，b，c，使得a + b + c = 0？ 查找數(shù)組中所有唯一的三元組，它們的總和為零。
注意：解決方案集不能包含重復(fù)的三元組。
例子：
給定數(shù)組：
S = [-1, 0, 1, 2, -1, -4]
解決方案：
在剛看到這道題目的題目的時(shí)候，首先想到的就是暴力解法，將數(shù)組排序后直接嵌套三個(gè)循環(huán)，這樣子雖然簡(jiǎn)單，但是時(shí)間復(fù)雜度確實(shí)n^3,遇到數(shù)據(jù)量過大的時(shí)候消耗太大，提交的時(shí)候并沒有通過。
自己在想了一段時(shí)間后想到了一些優(yōu)化方案，但是本質(zhì)上都沒有將次方縮減，所以仍然需要改進(jìn)，目標(biāo)為n^2。
首先，目標(biāo)為n^2的話，就需要將數(shù)組掃描兩遍，第一層循環(huán)沒有問題，但要將第二層和第三層循環(huán)縮減為掃描一遍，因?yàn)槭且獙蓚€(gè)數(shù)相加等于某個(gè)值，所以可將有序數(shù)組分別從前往后和從后往前掃描，直至碰頭，碰頭后如果繼續(xù)循環(huán)的話，所得到的結(jié)果會(huì)重復(fù)，
所以到碰頭后可以跳出循環(huán)。這樣子只需要掃描數(shù)組一遍就可達(dá)到兩層循環(huán)的結(jié)果。思路簡(jiǎn)單是這樣，在實(shí)現(xiàn)的時(shí)候要考慮一些其他的問題，具體實(shí)現(xiàn)的代碼如下：
public class Solution {
public ListListInteger>> threeSum(int[] nums) {
ListListInteger>> result = new LinkedListListInteger>>();
if(nums.length3){
return result;
}
Arrays.sort(nums);
int left=0,right=nums.length-1;
for(int mid=0;mid nums.length-2;mid++){
if(nums[mid]>0) break;
if(mid == 0 || (mid > 0 nums[mid] != nums[mid-1])){
left=mid+1;
right=nums.length-1;
while(leftright){
if(nums[left]+nums[mid]+nums[right] ==0){
result.add(Arrays.asList(nums[mid],nums[left],nums[right]));
while (left right nums[left] == nums[left+1]) left++;
while (left right nums[right] == nums[right-1]) right--;
left++;
right--;
}else if(nums[left]+nums[mid]+nums[right]0){
left++;
}else if(nums[left]+nums[mid]+nums[right]>0){
right--;
}
}
}
}
return result;
}
}
以上為個(gè)人經(jīng)驗(yàn)，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教。
您可能感興趣的文章:- golang簡(jiǎn)易令牌桶算法實(shí)現(xiàn)代碼
- 使用GO實(shí)現(xiàn)Paxos共識(shí)算法的方法
- 自己動(dòng)手用Golang實(shí)現(xiàn)約瑟夫環(huán)算法的示例
- 用go寫的五子棋預(yù)測(cè)算法的實(shí)現(xiàn)
- Golang實(shí)現(xiàn)拓?fù)渑判?DFS算法版)
