代码随想录 Day6 哈希 LeetcodeT454 四数之和II T383赎金信 T15 三数之和 T18 四数之和

本文代码思路来源于:

代码随想录

前言

希望大家在刷这部分题的时候先熟悉熟悉哈希结构的基本常用api,比较方便理解.

LeetCode T454 四数之和

题目链接:454. 四数相加 II - 力扣（LeetCode）

题目思路

暴力解法仍然是遍历四个数组解决此题,

哈希的思路有点类似于两数之和的解决方式,我们可以将四个数组分成两部分,数组1和数组2的和形成一个新数组(便于理解并没有去这样做,只是遍历两个数组),同理三四号数组也是一样,

1.首先我们创建一个HashMap,key放两数之和,value放和出现的次数

2.遍历数组1和数组2,将两数之和和出现次数放到map中

3.遍历数组3和数组4,在HashMap中查找是否存在0-前面的两数之和,存在就用res变量来记录

getOrDefault函数解释

代码示例

class Solution {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {Map<Integer,Integer> map = new HashMap<>();int res = 0;for(int i:nums1){for(int j:nums2){int sum = i+j;map.put(sum,map.getOrDefault(sum,0)+1);}}for(int i:nums3){for(int j :nums4){res+=map.getOrDefault(0-i-j,0);}}return res;}
}

LeetCode T383 赎金信

题目链接:383. 赎金信 - 力扣（LeetCode）

题目思路

这题乍一看有点像我们的相同字母的异序词那道题,那道题我们使用了哈希数组来实现,实际上这道题我们也能如法炮制,因为题目说了字符串全是小写字母,数量有限,很方便我们来映射,下面我们来说说基本步骤:

1.首先我们创建一个record数组用来当我们的哈希数组用来映射

2.然后我们将magazine字符串转成数组再用字符c遍历,c-'a'就是数组的下标,我们让这个位置的元素++即可

3.接着同理用字符c遍历ransomNote遍历,执行--操作

4.for循环遍历数组record,判断是否有小于0的数字,如果有,就返回false,没有就返回true.

代码实现

class Solution {public boolean canConstruct(String ransomNote, String magazine) {int[] record = new int[26];if(ransomNote.length()>magazine.length()){return false;}for(char c:magazine.toCharArray()){record[c-'a']++;}for(char c:ransomNote.toCharArray()){record[c-'a']--;}for(int j: record){if(j < 0){return false;}}return true;}
}

 LeetCode T15 三数之和

题目链接:15. 三数之和 - 力扣（LeetCode）

题目思路

使用双指针法,首先我们创建一个二维数组res,然后对数组进行排序.(降序排列)

总体思路是i指向第一个元素的下标,left指针指向i+1的下标,right指针指向length-1的下标,然后for循环遍历数组,首先判断i下标的值是否小于0,如果小于0则直接返回数组元素,如果不是则进行判断,三数之和大于0的话,则应该让right向前走,反之则让left向后走,好了,剩下就是处理细节的去重操作了.也是本题的精华所在

去重逻辑的思考 

首先这里我们知道,三数之和不能取重复的三元组,比如 {1,1,-1,0},这里的{1,-1,0}这个三元组只能取一次,那么我们就要进行去重,首先对nums[i]进行去重,这里有两种去重方式,第一种是nums[i]和nums[i+1]进行比较,还有一种是nums[i]和nums[i-1]进行比较,我们到底选哪一种呢?
 

我们不妨就{-1,-1,2}这个例子来看,如果我们选择了第一种去重方式,那么我们就会发现,当遍历到第一个-1的时候,判断下一个也是-1,那这组数据就直接被pass了,这里强调一下我们要的三元组组内数据可以重复,但是三元组不能重复,例如{0,0,0}也是满足要求的一个三元组.

所以对于第一个去重操作,我们应该这样写:

if (i > 0 && nums[i] == nums[i - 1]) {continue;
}

接下来就是对nums[right]和nums[left]进行去重,我们知道数组是排好序的,如果三个数加起来是大于0的,我们就可以让right指针向前走,反之我们应该让left指针向后走.

但细想一下，这种去重其实对提升程序运行效率是没有帮助的.

拿right去重为例，即使不加这个去重逻辑，依然根据 while (right > left) 和 if (nums[i] + nums[left] + nums[right] > 0) 去完成right-- 的操作。

多加了 while (left < right && nums[right] == nums[right + 1]) right--; 这一行代码，其实就是把 需要执行的逻辑提前执行了，但并没有减少 判断的逻辑。

最直白的思考过程，就是right还是一个数一个数的减下去的，所以在哪里减的都是一样的。

所以这种去重 是可以不加的。 仅仅是 把去重的逻辑提前了而已。

代码实现

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;}              if(i>0 && nums[i-1] == nums[i]){continue;} int left = i+1;int right = nums.length-1;while(left<right){int  sum = nums[i] + nums[left] + nums[right];if(sum >0){right--;}else if(sum<0){left++;}else{res.add(Arrays.asList(nums[i],nums[left],nums[right]));while(left<right && nums[right] == nums[right-1]){right--;}while(left<right &&nums[left] == nums[left + 1] ){left++;}left++;right--;}}}return res;}
}

LeetCode T18 四数之和

题目链接:18. 四数之和 - 力扣（LeetCode）

 

题目思路

本质上就是在三数之和,外面再套了一层for循环,重点就是这个去重的过程如何进行,下面我们来仔细分析一下去重的过程

去重的思路 

有人可能上来就按照三数之和的思路上来就判断nums[i]和target的大小,这里就出问题了,首先三数之和保证了target是0,这里target不知道是多少,所以我们要保证我们的nums[i]>0才可以,不然两个负数相加也可以越加越小啊,这明显不满足题目要求,我们注意这里虽然是排好序的数字,但是直接用nums[i]和target做判断未免太过武断,综上所述我们是这样操作的.

if (nums[i] > 0 && nums[i] > target) {return result;
}

然后进行和三数之和一样的去重操作

if(i>0 && nums[i] == nums[i-1])
{continue;
}

接着第二层for循环,先剪枝去重,接着进行双指针

 if(nums[i]+ nums[j]>target && nums[i]>=0){return result;}if(j>i+1 && nums[j] == nums[j-1]){continue;}

代码实现

class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>> result = new ArrayList<>();Arrays.sort(nums);for(int i = 0;i<nums.length;i++){//一级剪枝if(nums[i]>target && nums[i]>0){return result;}if(i>0 && nums[i] == nums[i-1]){continue;}for(int j = i+1;j<nums.length;j++){if(nums[i]+ nums[j]>target && nums[i]>=0){return result;}if(j>i+1 && nums[j] == nums[j-1]){continue;}int left = j+1;int right = nums.length-1;while(right>left){long sum = nums[i] + nums[j] + nums[left] + nums[right];if(sum>target){right--;}else if(sum < target){left++;}else{result.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));while(right>left && nums[left] == nums[left+1] ){left++;}while(right>left && nums[right] == nums[right-1]){right--;}left++;right--;}}}}return result;}
}