快捷導(dǎo)航

go語言的四數(shù)相加等于指定數(shù)算法

更新時(shí)間：2021年04月27日 10:47:32 作者：力扣（LeetCode）

這篇文章主要介紹了go語言的四數(shù)相加等于指定數(shù)算法的操作，具有很好的參考價(jià)值，希望對大家有所幫助。一起跟隨小編過來看看吧

給定四個(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]

解決方案：

[[-1, 0, 1],[-1, -1, 2]]

在剛看到這道題目的題目的時(shí)候，首先想到的就是暴力解法，將數(shù)組排序后直接嵌套三個(gè)循環(huá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é)果會重復(fù)，

所以到碰頭后可以跳出循環(huán)。這樣子只需要掃描數(shù)組一遍就可達(dá)到兩層循環(huán)的結(jié)果。思路簡單是這樣，在實(shí)現(xiàn)的時(shí)候要考慮一些其他的問題，具體實(shí)現(xiàn)的代碼如下：

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new LinkedList<List<Integer>>();
        if(nums.length<3){
            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(left<right){
                    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ò)誤或未考慮完全的地方，望不吝賜教。

您可能感興趣的文章: