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