454.四数相加II
题目链接 | 文档讲解 |视频讲解 : 链接
1.思路：
0.定义一个count，计算最终出现的次数
1.先遍历nums1和nums2,求出两者的和，map的key是和，value是出现的次数
2.再遍历nums3和nums4，求出0-两者的和
3.判断map集合中是否出现 0-两者的和,出现过count+map的value值，否则为count+0
【注】不能是count++,因为在记录nums1和nums2，[1,2] [2,1] key=3的出现过2次，value存的是2，count+的是value值
2.代码：
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
int count=0;
Map<Integer,Integer> map=new HashMap<>();
//key是 nums1[i]+nums[j]的值 value是出现的次数
for (int a : nums1) {
for (int b : nums2) {
// if(map.containsKey(a+b)){
// map.put(a+b,map.get(a+b)+1);
// }else {
// map.put(a+b,1);
// }
//使用map.getOrDefault()方法，无需在if判断，不存在,value为默认值0，存在则获取对应的值
map.put(a+b,map.getOrDefault(a+b,0)+1);
}
}
for (int c : nums3) {
for (int d : nums4) {
// if(map.containsKey(0-c-d)){
// count+=map.get(0-c-d);
// }
count+=map.getOrDefault(0-c-d,0);
}
}
return count;
}15. 三数之和
题目链接 | 文档讲解 |视频讲解：链接
1.思路：
1.先排序，第一个元素>0,直接返回空集合
2.使用for循环+双指针, 初始时左指针指向第二个元素，右指针指向最后一个元素
3.去重操作,for循环的当前元素和上一个元素相等，continue eg: -1 -1 0 1 避免出现重复的三元数组 2个[-1 0 1]
4.循环判断条件，左右指针不能相等，因为求是3个元素相加和，相等成了2个元素的和，判断三数之和num ,num>0,right--, num<0,left++ , num==0,收集三元数组，left++ right-- 【注】==0时，去重判断，left和left-1是否相等，right和right+1是否相等，避免出现 -1 0 0 1 1 ，2个[-1 0 1]
2.代码：
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result=new ArrayList();
//1.排序
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
//第一个元素大于0,就不会出现和为0的数组了
if(nums[i]>0){
return result;
}
//三元数组不能重复,eg: -1 -1 0 1
// 第一次循环 i指向第一个-1，得出了三元数组[-1 0 1]
// 第二次循环 i指向第二个-1,再次得出了三元数组[-1 0 1],与题目要求不符，所以在这里要进行去重判断
//为什么不是和其下一个元素进行比较，而是和当前元素的前一个比较呢？
if(i>0 && nums[i]==nums[i-1]){
continue;
}
int left=i+1;
int right=nums.length-1;
while (left<right){
int num=nums[i]+nums[left]+nums[right];
//num>0,说明right需要变小
if(num>0){
right--;
}
//num>0,说明left需要变大
if(num<0){
left++;
}
if(num==0){
List<Integer> list=new ArrayList<>();
list.add(nums[i]);
list.add(nums[left]);
list.add(nums[right]);
result.add(list);
left++;
right--;
//因为left在上面已经+1,,所以需要与其前一个元素进行比较
//避免出现-2 0 0 1 2 2 避免出现2个 [-2,0,2]
while (left<right && nums[left]==nums[left-1]){
left++;
}
//因为right在上面已经-1,所以需要与其后面一个元素进行比较
while (left<right && nums[right]==nums[right+1]){
right--;
}
}
}
}
return result;
}
18. 四数之和
题目链接 | 文档讲解 |视频讲解：链接
1.思路：
排序
2层for循环+双指针
第一层for循环：判断nums[i]>0 && nums[i]>target,返回空集合。必须判断nums[i]>0,因为如果是负数，会出现 [-5,-1 ,0 ,0] target= -6 ，判断当前元素和其上一个元素是否相等，相等，continue,退出本次循环
第二层for循环：nums[i]+nums[j]>0 && nums[i]+nums[j]>target，break,退到上一层循环，避免出现 [-5,-1 ,0 ,1] target=-7 ， 判断当前元素和其上一个元素是否相等，相等，continue,退出本次循环
while循环，左右指针的移动柜规则同三数之和，在这里不做赘述
2.代码：
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> result =new ArrayList<>();
//1.排序
Arrays.sort(nums);
//2层for循环+双指针
for (int i = 0; i < nums.length; i++) {
// 【注】：不能直接判断nums[i]>target 避免出现 [-5,-1 ,0 ,0] target= -6 -5>-6但是会出现符合条件的四元数组,
//数组中存在负数，是有可能会越加越小的
if(nums[i]>0 && nums[i]>target){
return result;
}
//一级去重
if(i>0 && nums[i]==nums[i-1]){
continue;
}
for (int j = i+1; j < nums.length; j++) {
// 【注】：不能直接判断nums[i]+nums[j]>target,避免出现 [-5,-1 ,0 ,1] target=-7 -5+(-1)>-7 但是会出现符合条件的四元数组
if(nums[i]+nums[j]>0 && nums[i]+nums[j]>target){
break;
}
//二级去重
if(j>i+1 && nums[j]==nums[j-1]){
continue;
}
int left=j+1;
int right=nums.length-1;
//下面同三元数组之和
while (left<right){
int num=nums[i]+nums[j]+nums[left]+nums[right];
if(num>target){
right--;
}
if(num<target){
left++;
}
if(num==target){
List<Integer> list=new ArrayList<>();
list.add(nums[i]);
list.add(nums[j]);
list.add(nums[left]);
list.add(nums[right]);
result.add(list);
left++;
right--;
while (left<right && nums[left]==nums[left-1]){
left++;
}
while (left<right && nums[right]==nums[right+1]){
right--;
}
}
}
}
}
return result;
}