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

給定四個包含整數的數組列表 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。如有錯誤或未考慮完全的地方,望不吝賜教。

推薦閱讀: