本文代码思路来源于:
前言
希望大家在刷这部分题的时候先熟悉熟悉哈希结构的基本常用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 赎金信
题目思路
这题乍一看有点像我们的相同字母的异序词那道题,那道题我们使用了哈希数组来实现,实际上这道题我们也能如法炮制,因为题目说了字符串全是小写字母,数量有限,很方便我们来映射,下面我们来说说基本步骤:
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 三数之和
题目思路
使用双指针法,首先我们创建一个二维数组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 四数之和
题目思路
本质上就是在三数之和,外面再套了一层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; } }
