语言
采用的Java语言，一些分析也是用于Java，请注意。
454.四数相加II
454. 四数相加 II - 力扣（LeetCode）
这道题理解好只是统计数量即可，不需要去重，因此很简单的题目。
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < nums1.length; i++) {
for(int j = 0;j<nums2.length;j++){
int sum = nums1[i] + nums2[j];
// map.put(sum,map.getOrDefault(sum,0)+1);
if(!map.containsKey(sum)){
map.put(sum,1);
}else {
map.put(sum,map.get(sum)+1);
}
}
}
int res = 0;
for (int i = 0; i < nums3.length; i++) {
for (int j = 0; j < nums4.length; j++) {
int sum = nums3[i]+nums4[j];
// res+=map.getOrDefault(sum,0);
if(map.containsKey(0-sum)){
res+=map.get(0-sum);
}
}
}
return res;
}
}383. 赎金信
383. 赎金信 - 力扣（LeetCode）
这个题很简单。
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
int [] hash = new int[26];
// a a b
// 2 1
for (int i = 0; i < magazine.length(); i++) {
hash[magazine.charAt(i)-'a']++;
}
for (int i = 0; i < ransomNote.length(); i++) {
hash[ransomNote.charAt(i)-'a']--;
}
for (int i = 0; i < hash.length; i++) {
if(hash[i]<0){
return false;
}
}
return true;
}
}15. 三数之和
15. 三数之和 - 力扣（LeetCode）
这道题有三个注意的地方
1、对i去重的时候是要i和i-1， 因为要先把结果拿到，再做去重
2，对于left和right去重的位置也要注意，也是要拿到结果，再去重，所以放后面
3、对于==之后做left++和right--放在while的前面还是后面
这里给出来了例子，应该是放到后面才对，放前面的话就归到剪枝的逻辑去了，结果就会重复。
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
if(nums[i]>0){return res;}
//对i去重
if(i>0&&nums[i]==nums[i-1]){//i 和 i+1的话，会少情况，比如-1，-1，2
//意思就是-1，-1 2 的时候要先收集，下一步再跳过去去重
continue;
}
int left = i+1;
int right = nums.length-1;
while(right>left){//=的时候不符合条件，因为有三个数
int sum = nums[i]+nums[left]+nums[right];
if(sum>0){
right--;
}else if(sum<0){
left++;
}else {
List<Integer> subRes = Arrays.asList(nums[i], nums[left], nums[right]);
res.add(subRes);
//去重 //[-1,-1,0,1 1 1]
while(right>left && nums[left]==nums[left+1]) left++;
while(right>left && nums[right]==nums[right-1]) right--;
//-1，0,1
left++;
right--;
}
}
}
return res;
}
}18. 四数之和
18. 四数之和 - 力扣（LeetCode）
注意点1：
第一个剪枝可直接return res，因为数组排序好的，比如
target = -1 nums: -2 -2 0 0 1 2 4 5
k 第一次= -2 然后，下一次循环的时候，-2 continue，=0的时候，发现大于0 了，那么后面的数都大于9，就可以不用算了。再怎么相加都会大于target，因为k=0的时候，后面的i 和left right加起来肯定时大于target的
若刚开始的nums就是 0 1 2 3 4 这样大于=0 的，就更符合剪枝的逻辑了
举这个例子的时候，就是为了解释，为什么这里可以直接return
那么为什么二级减枝不可以直接retrun呢？
这里就需要注意了，第二层循环的时候，比如-2 -1 0 0 1 2的时候，k=-2 i=2>=target的时候，符合条件，并不影响下一次的-1和0<target.这是需要注意的，看这里的模拟
注意点2：
剪枝逻辑里 是nums[k]>target&&nums[k]>0还是nums[k]>target&&target>0
nums[k] > target && nums[k] > 0 这个条件表示的含义是，如果当前值比 target 大，并且后面再加其他值还是比 target 大说明当前这个值不用往后选了，nums[k] > 0 就是用来保证 k 位置后面的值比当前值大的。 但是你写成 target > 0 无形中就把范围收窄了
所以推荐nums[k]>target&&nums[k]>0,可以把条件缩小，剪枝多一点，
这道题用另一种写法的话会报错误，应该是int类型溢出的问题，可以替换代码试一下
注意点3
continue可不可以写成i++、k++
比如-1 -1 -1,0
k在第二个-1的时候，continue下一次到0了，但是认为k++也可以满足到0 ，其实是只会++一次，continue可以做到移动到0
有人说那改成while不就好了，while和i++，这就需要考虑其他问题，舍本逐末，不要和我一样钻牛角尖。
解题
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(nums);
for (int k = 0; k < nums.length; k++) {
//剪枝
if(nums[k]>target&&nums[k]>=0){
return res;
}
//去重 -1 -1 0
if(k>0&&nums[k]==nums[k-1]) continue;
for (int i = k+1; i < nums.length; i++) {
//剪枝
int sum1 = nums[k]+nums[i];
if(sum1>target&&sum1>=0) break;
//去重
if(i>k+1&&nums[i]==nums[i-1]) continue;
//left和right去重
int left = i+1;
int right = nums.length-1;
while(right>left){
long sum = sum1+nums[left]+nums[right];
if(sum>target){
right--;
} else if (sum < target) {
left++;
}else {
List<Integer> subRes = Arrays.asList(nums[k], nums[i], nums[left], nums[right]);
res.add(subRes);
while (right>left&&nums[right]==nums[right-1])right--;
while (right>left&&nums[left]==nums[left+1])left++;
left++;
right--;
}
}
}
}
return res;
}
}总结
hash表这里每个博客都分析了一下，就不做总结了，这个四数之和挺累的，长脑子了，方便我复习，就把卡哥的总结放这里了，方便我和读者回顾。
代码随想录 (programmercarl.com)
