go語言的四數相加等於指定數算法

Posted on by

給定四個包含整數的數組列表 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]

解決方案：

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

在剛看到這道題目的題目的時候，首先想到的就是暴力解法，將數組排序後直接嵌套三個循環，這樣子雖然簡單，但是時間復雜度確實n^3,遇到數據量過大的時候消耗太大，提交的時候並沒有通過。

自己在想瞭一段時間後想到瞭一些優化方案，但是本質上都沒有將次方縮減，所以仍然需要改進，目標為n^2。

首先，目標為n^2的話，就需要將數組掃描兩遍，第一層循環沒有問題，但要將第二層和第三層循環縮減為掃描一遍，因為是要將兩個數相加等於某個值，所以可將有序數組分別從前往後和從後往前掃描，直至碰頭，碰頭後如果繼續循環的話，所得到的結果會重復，

所以到碰頭後可以跳出循環。這樣子隻需要掃描數組一遍就可達到兩層循環的結果。思路簡單是這樣，在實現的時候要考慮一些其他的問題，具體實現的代碼如下：

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;
    }
}

以上為個人經驗，希望能給大傢一個參考，也希望大傢多多支持WalkonNet。如有錯誤或未考慮完全的地方，望不吝賜教。

推薦閱讀：