哈希的第二天，有了昨天的刷题基础，今天写Hash能顺手一些啦！
第454题.四数相加II
题目描述：
给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：
- 0 <= i, j, k, l < n
- nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
解题思路：
- 初始化一个hashmap来存储num1和num2中元素两两相加的和；和为key，出现的次数为value；
- 将num3和num4中的元素也两两相加，如果存在0-(num3+num4)，则计数；
- 用变量res来储存这个计数，并返回。
思考：
为什么选择用HashMap？
- 四个数组里的元素都是int型，可能很大，无法控制，不像第242题，因此我们不能用数组的下标来定位元素，这样会使数组的空间很大，资源浪费；
- 我们不仅要储存两两相加的和，还要统计次数，因此需要使用Map结构，因为它有key和value；
- 最终思路中我们需要快速查找某一元素，符合使用Hash的原则。且元素可以重复！！
因此，我们选择HashMap
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
int res = 0;
Map<Integer, Integer> map = new HashMap<>();
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){
//写法二
if(map.containsKey(0-(i+j))){
res += map.get(0-(i+j));
}
}
}
return res;
}
}
第15题. 三数之和
题目描述：
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
解题思路：
运用数组+排序+双指针
1.将数组进行排序，设定数组头i，左指针left位i+1，右指针right为数组末位
2.进行循环遍历，sum为i+left+right
·若sum大于0，说明大的数要缩小，right往前进位
·若sum小于0，说明和太小，要增大小的数，left往后进位
·直到sum为0，返回res
思考：
为什么这一题不用Hash？
因为这道题的要求是结果中不能出现重复数组；用hash的话，去重太麻烦。
如何去重？
这道题重点为去重操作，因为不能出现重复的元组。不可以出现重复的结果数组，但是数组中可以出现重复元素，因此我们的去重是和前一个元素进行比较。而不是后一个元素。如果和后一个元素进行比较的话，会导致结果集中[-1,-1,2]，这样的结果被跳过。
为什么两数之和不能用双指针？
因为两数之和返回索引，并不是返回值；双指针要重新排序，index会乱。
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
//将nums进行排序
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
//因为已经进行排序，如果第一个数就大于0，则三数相加肯定大于0，跳出
if (nums[i] > 0) return res;
//去重，对第一位去重
//如果后面一个数等于前面一个数，就判断过了，无需再判断
if (i > 0 && nums[i] == nums[i - 1]) {continue;}
//设置双指针，left为i后面一位；right为数组末位
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]));
//去重
/*
大前提：left < right
当left后面的数有跟当前left重合时，将left向后移一位
当right前面的数有跟当前right相同时，将right向前移一位
*/
while (left < right && nums[right] == nums[right - 1]) right--; //对第二位的去重
while (left < right && nums[left] == nums[left + 1]) left++; //对第三位的去重
right--;
left++;
}
}
}
return res;
}
}
第18题. 四数之和
题目描述：
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
- 0 <= a, b, c, d < n
- a、b、c 和 d 互不相同
- nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案。
解题思路：
思路与三数之和差不多，在三数之和的基础上，再加一层for循环
Tipp：
注意去重的条件
·每一种循环枚举到的下标必须大于上一重循环枚举到的下标；
·同一重循环中，如果当前元素与上一个元素相同，则跳过当前元素。
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++){
//剪枝，确保nums[k]>target,因为 target 有可能是复数
if(nums[k]>0 && nums[k]>target){
return res;
}
//对 k 去重
if(k>0 && nums[k] == nums[k-1]) continue;
//以下和三数之和相同
for(int i = k+1; i<nums.length; i++){
if(i>k+1 && nums[i-1]==nums[i]){
continue;
}
int left = i+1;
int right = nums.length - 1;
while(right > left){
long sum = nums[k] + nums[i] + nums[left] + nums[right];
if(sum > target){
right--;
}else if(sum < target){
left++;
}else{
res.add(Arrays.asList(nums[k], nums[i], nums[left], nums[right]));
//对 left 和 right去重
while(right>left && nums[left] == nums[left+1]) left++;
while(right>left && nums[right] == nums[right-1]) right--;
left++;
right--;
}
}
}
}
return res;
}
}
383. 赎金信
题目描述：
给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以，返回 true ；否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。
解题思路：
比较字符串
1.用数组count来记录每个字母出现的频率
2.分别遍历magazine(++)和ransomNote(--)中每个字母的出现次数，进行比较
3.若count中出现负数，则m中的某个字符个数小于r中的，则返回false
lass 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']=record[c-'a']+1;
}
for(char c: ransomNote.toCharArray()){
record[c-'a'] =record[c-'a']-1;
}
for(int i: record){
if(i < 0){
return false;
}
}
return true;
}
}
