给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。
首先将四个数组分割为两两数组，前两个数组值相加，后两个数组相加，入股前两个数组相加和与后两个数组相加和正好为相反数，四个元素之和为0.
首先：
将两数组的元素进行遍历相加，相加之和为map的索引。所指向的元素，就是出现的次数。
|
1
2
3
4
5
6
7
8
|
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，如果出现过这个数的相反数，则所指向的数大于一。
|
1
2
3
4
5
6
7
8
9
|
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]
}
}
}
|
最后将总数返回
全部代码
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
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？ 查找数组中所有唯一的三元组，它们的总和为零。
注意：解决方案集不能包含重复的三元组。
例子：
给定数组：
|
1
|
S = [-1, 0, 1, 2, -1, -4]
|
解决方案：
|
1
|
[[-1, 0, 1],[-1, -1, 2]]
|
在刚看到这道题目的题目的时候，首先想到的就是暴力解法，将数组排序后直接嵌套三个循环，这样子虽然简单，但是时间复杂度确实n^3,遇到数据量过大的时候消耗太大，提交的时候并没有通过。
自己在想了一段时间后想到了一些优化方案，但是本质上都没有将次方缩减，所以仍然需要改进，目标为n^2。
首先，目标为n^2的话，就需要将数组扫描两遍，第一层循环没有问题，但要将第二层和第三层循环缩减为扫描一遍，因为是要将两个数相加等于某个值，所以可将有序数组分别从前往后和从后往前扫描，直至碰头，碰头后如果继续循环的话，所得到的结果会重复，
所以到碰头后可以跳出循环。这样子只需要扫描数组一遍就可达到两层循环的结果。思路简单是这样，在实现的时候要考虑一些其他的问题，具体实现的代码如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
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;
}
}
|
以上为个人经验，希望能给大家一个参考，也希望大家多多支持服务器之家。如有错误或未考虑完全的地方，望不吝赐教。
原文链接：https://leetcode-cn.com/problems/4sum-ii/