代码随想录算法训练第七天，继续哈希表
今日任务
● 454.四数相加II
● 383. 赎金信
● 15. 三数之和
● 18. 四数之和
● 总结
454. 四数相加II
给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。
思路：
将四个数组 简化成two sum 问题， 具体步骤：
- 首先定义 一个unordered_map，key放a和b两数之和，value 放a和b两数之和出现的次数。
- 遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中。
- 定义int变量count，用来统计 a+b+c+d = 0 出现的次数。
- 再遍历大C和大D数组，找到如果 0-(c+d) 在map中出现过的话，就用count把map中key对应的value也就是出现次数统计出来。
- 最后返回统计值 count 就可以了
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
Map<Integer, Integer> adSum = new HashMap<Integer, Integer>();
int resCount = 0; // result
//save sum of A, B, and occurrence
for(int i = 0; i < nums1.length; i++){
for(int j = 0; j < nums2.length; j++){
int sum = nums1[i] + nums2[j];
if(adSum.containsKey(sum)){
//put() will override old value
adSum.put(sum, adSum.get(sum) + 1);
}else{
adSum.put(sum, 1);
}
}
}
//iterate C and D, find if 0-(c+d) exist in map
for(int i = 0; i < nums3.length; i++){
for(int j = 0; j < nums4.length; j++){
int sum = nums3[i] + nums4[j];
int target = 0 - sum;
if(adSum.containsKey(target)){
resCount += adSum.get(target);
}
}
}
return resCount;
}
}
时间复杂度： O(nn)
空间复杂度： O(nn) 哈希映射需要的空间， 最差情况下A[i] + B[j]值均不相同，需要n*n
-
赎金信
给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。
(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)
你可以假设两个字符串均只含有小写字母。
本题 和 242.有效的字母异位词 是一个思路
因为题目所只有小写字母，那可以采用空间换取时间的哈希策略， 用一个长度为26的数组还记录magazine里字母出现的次数。
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
if(ransomNote.length() > magazine.length()) return false;
int[] avaliableLetters = new int[26];
//for(char c : magazine.toCharArray())
for(int i = 0; i < magazine.length(); i++){
avaliableLetters[magazine.charAt(i) - 'a']++;
}
for(int i = 0; i < ransomNote.length(); i++){
int index = ransomNote.charAt(i) - 'a';
avaliableLetters[index]--;
if(avaliableLetters[index] < 0) return false;
}
return true;
}
}
15. 三数之和
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意： 答案中不可以包含重复的三元组。
双指针算法：
对数组进行排序
遍历排序后数组：
- 若 nums[i]>0：因为已经排序好，所以后面不可能有三个数加和等于 0，直接返回结果。
- 对于重复元素：跳过，避免出现重复解
- 令左指针 L=i+1，右指针 R=n−1，当 L<R 时，执行循环：
-当 nums[i]+nums[L]+nums[R]==0，执行循环，判断左界和右界是否和下一位置重复，去除重复解。并同时将 L,R 移到下一位置，寻找新的解
- 若和大于 0，说明 nums[R] 太大，R 左移
- 若和小于 0，说明 nums[L] 太小，L 右移
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> resList = new ArrayList<>();
//original order doesnt matter for return result
//sort the array, use left,right pointer to get sum of triplets
Arrays.sort(nums);
int n = nums.length;
//if smallest number > 0 or largest number < 0, wont find any qualifying triplets
if(nums[0] > 0 || nums[n - 1] < 0) return resList;
for(int i = 0; i < n - 2; i++){
//skip duplicates for first number
if(i > 0 && nums[i] == nums[i - 1]) continue;
//left points to the smallest number besides i
//right points to the largest number besides i
int left = i + 1, right = n - 1;
while(left < right){
int sum = nums[i] + nums[left] + nums[right];
if(sum > 0){
//nums[left] + nums[right] needs to be smaller to get sum to 0
right--;
}else if(sum < 0){
//nums[left] + nums[right] needs to be bigger to get a 0 sum
left++;
}else{
//triplet found
resList.add(Arrays.asList(nums[i],nums[left],nums[right]));
//skip duplicates
while(left < right && nums[left] == nums[left + 1]) left++;
while(left < right && nums[right] == nums[right - 1]) right--;
//increment to process next combination
left++;
right--;
}
}
}
return resList;
}
}
时间复杂度 O(n * n) : 数组排序O(nlogn); 固定指针i 循环复杂度 O(N), 双指针遍历O(N)
空间复杂度O(1)
18. 四数之和
对于15.三数之和 (opens new window)双指针法就是将原本暴力O(n3)的解法，降为O(n2)的解法，四数之和的双指针解法就是将原本暴力O(n4)的解法，降为O(n3)的解法。
哈希表的经典题目：454.四数相加II (opens new window)，相对于本题简单很多，因为本题是要求在一个集合中找出四个数相加等于target，同时四元组不能重复。而454是四个独立的数组，只要找到A[i] + B[j] + C[k] + D[l] = 0就可以，不用考虑有重复的四个元素相加等于0的情况。所以可以利用hashmap存储A[i] + B[j]之和，将之变形为O(n*n) 解法
思路：
四数之和与前面三数之和的思路几乎是一样的，
其实就是在三数之和的基础上多添加一个遍历的指针而已。
- 使用四个指针(i<j<left<right)。固定最小的a和b在左边，c=b+1,d=_size-1 移动两个指针包夹求解。
保存使得nums[i]+nums[j]+nums[left]+nums[right]==target的解。偏大时d左移，偏小时c右移。
left和right相遇时，表示以当前的i和j为最小值的解已经全部求得。j++,进入下一轮循环j循环，当j循环结束后。 i++，进入下一轮i循环。 即(i在最外层循环，里面嵌套j循环，再嵌套双指针left,right包夹求解)。
a遍历O(N)里嵌套b遍历O(N)再嵌套c,d双指针O(N)--> O(N^3)。 比暴力法O(N^4)好些吧。
但是有一些细节需要注意，例如： 不要判断nums[k] > target 就返回了，三数之和 可以通过 nums[i] > 0 就返回了，因为 0 已经是确定的数了，四数之和这道题目 target是任意值。比如：数组是[-4, -3, -2, -1]，target是-10，不能因为-4 > -10而跳过。
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> resList = new ArrayList<>();
Arrays.sort(nums);
int n = nums.length;
if(n < 4) return resList;
int left,right;
long sum;
for(int i = 0; i < n - 3; i++){
//remove duplicate
if(i > 0 && nums[i] == nums[i - 1]) continue;
for(int j = i + 1; j < n - 2; j++){
//remove duplicate, notice j lower bound value
if( j > i + 1 && nums[j] == nums[j - 1]) continue;
left = j + 1;
right = n - 1;
while(left < right){
sum = (long)nums[i] + nums[j] + nums[left] + nums[right];
if(sum < target){
left++;
}else if(sum > target){
right--;
}else{
//quadruplets found
resList.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
while(left < right && nums[left] == nums[left + 1]) left++;
while(left < right && nums[right] == nums[right-1]) right--;
left++;
right--;
}
}
}
}
return resList;
}
}
总结：
注意三种哈希结构的不同应用场景
数组：
242.有效的字母异位词 (opens new window)是求 字符串a 和 字符串b 是否可以相互组成，在383.赎金信 (opens new window)中是求字符串a能否组成字符串b，而不用管字符串b 能不能组成字符串a。
使用map的空间消耗要比数组大一些，因为map要维护红黑树或者符号表，而且还要做哈希函数的运算。所以数组更加简单直接有效！set（集合）
数组的大小是有限的，受到系统栈空间（不是数据结构的栈）的限制。
如果数组空间够大，但哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。更适合setmap（映射） store <key, value> pair
使用用例： 1.两数之和， 454.四数相加
使用数组和set来做哈希法的局限:
数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。
set是一个集合，里面放的元素只能是一个key，而两数之和这道题目，不仅要判断y是否存在而且还要记录y的下标位置，因为要返回x 和 y的下标。所以set 也不能用。
map是一种<key, value>的结构，本题可以用key保存数值，用value在保存数值所在的下标。所以使用map最为合适。
