Given four array lists of integers A , B , C , D , calculate how many tuples (i, j, k, l) there are, such that A[i] + B[j] + C[k] + D[l] = 0.
First, divide the four arrays into two pairs of arrays, add the values of the first two arrays, add the last two arrays, add the sum of the first two arrays and add the sum of the last two arrays to the next two arrays is exactly the opposite number, and the sum of the four elements is 0.
first:
The elements of the two arrays are traversed and added, and the sum of the addition is the index of the map. The element pointed to is the number of occurrences.
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]++
}
}
}
Iterate over the other two arrays again, add the elements of the two arrays, take the opposite number of the sum, and look up in the map by using the opposite number. If it does not appear, the number pointed to is 0. If the opposite number of this number appears, the number pointed to is greater than one.
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]
}
}
}
Finally return the total number
All codes
func fourSumCount(A []int, B []int, C []int, D []int) int {
des := map[int]int{}
ans:=0
for _,v :=range A{//Transfuse two arrays, use the sum of the two arrays as an index, and perform +1 operation for _,w:=range B{
des[v+w]++
}
}
for _,v :=range C{//Transfer through the other two arrays. If the opposite number of the sum of these two arrays is not 1 in the map, it is proved that it has for _,w:=range D{
ans +=des[-v-w]
}
}
return ans//Return the total number}
Supplementary: Algorithm Problem: Adding three numbers is equal to a specific value
The question comes from leetcode question 15
Given an array S with n integers, do the elements a, b, and c in S exist, such that a + b + c = 0? Find all unique triples in the array, and their sum is zero.
Note: Solution sets cannot contain duplicate triples.
example:
Given array:
S = [-1, 0, 1, 2, -1, -4]
Solution:
[[-1, 0, 1],[-1, -1, 2]]
When I first saw the question of this question, the first thing I thought of was the brute force solution, sorting the array and nesting three loops directly. Although this is simple, the time complexity is indeed n^3. When the data volume is too large, it consumes too much and it is not passed when submitting.
After thinking about it for a while, I thought of some optimization solutions, but in essence, I did not reduce the power to the point, so I still need to improve it, with the goal of n^2.
First, if the target is n^2, you need to scan the array twice. There is no problem with the first layer loop, but the second and third layer loops need to be reduced to scan one by one. Because the two numbers are added equal to a certain value, the ordered array can be scanned from front to back and back to front until the head is met. If the loop continues after the head is met, the result will be repeated.
So you can jump out of the loop after the encounter. In this way, you only need to scan the array once to achieve the result of two-layer loops. The idea is simple, so you need to consider some other issues when implementing it. The specific implementation code is as follows:
public class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new LinkedList<List<Integer>>();
if(<3){
return result;
}
(nums);
int left=0,right=-1;
for(int mid=0;mid< -2;mid++){
if(nums[mid]>0) break;
if(mid == 0 || (mid > 0 && nums[mid] != nums[mid-1])){
left=mid+1;
right=-1;
while(left<right){
if(nums[left]+nums[mid]+nums[right] ==0){
((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;
}
}
The above is personal experience. I hope you can give you a reference and I hope you can support me more. If there are any mistakes or no complete considerations, I would like to give you advice.