代碼隨想錄算法訓練第七天，繼續(xù)哈希表
今日任務
● 454.四數(shù)相加II
● 383. 贖金信
● 15. 三數(shù)之和
● 18. 四數(shù)之和
● 總結(jié)
454. 四數(shù)相加II
給定四個包含整數(shù)的數(shù)組列表 A , B , C , D ,計算有多少個元組 (i, j, k, l) 裕坊，使得 A[i] + B[j] + C[k] + D[l] = 0制跟。
思路：
將四個數(shù)組 簡化成two sum 問題邻邮， 具體步驟：
- 首先定義 一個unordered_map，key放a和b兩數(shù)之和路媚，value 放a和b兩數(shù)之和出現(xiàn)的次數(shù)谐腰。
- 遍歷大A和大B數(shù)組杰捂，統(tǒng)計兩個數(shù)組元素之和翰灾，和出現(xiàn)的次數(shù)哮肚，放到map中停局。
- 定義int變量count很钓，用來統(tǒng)計 a+b+c+d = 0 出現(xiàn)的次數(shù)。
- 再遍歷大C和大D數(shù)組董栽，找到如果 0-(c+d) 在map中出現(xiàn)過的話码倦，就用count把map中key對應的value也就是出現(xiàn)次數(shù)統(tǒng)計出來。
- 最后返回統(tǒng)計值 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 里面的字符構(gòu)成擒抛。如果可以構(gòu)成推汽，返回 true ；否則返回 false歧沪。
(題目說明：為了不暴露贖金信字跡歹撒，要從雜志上搜索各個需要的字母，組成單詞來表達意思诊胞。雜志字符串中的每個字符只能在贖金信字符串中使用一次暖夭。)
你可以假設兩個字符串均只含有小寫字母。
本題 和 242.有效的字母異位詞 是一個思路
因為題目所只有小寫字母撵孤，那可以采用空間換取時間的哈希策略迈着， 用一個長度為26的數(shù)組還記錄magazine里字母出現(xiàn)的次數(shù)。
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. 三數(shù)之和
給你一個包含 n 個整數(shù)的數(shù)組 nums早直，判斷 nums 中是否存在三個元素 a寥假，b市框，c 霞扬，使得 a + b + c = 0 ？請你找出所有滿足條件且不重復的三元組枫振。
注意： 答案中不可以包含重復的三元組喻圃。
雙指針算法：
對數(shù)組進行排序
遍歷排序后數(shù)組：
- 若 nums[i]>0：因為已經(jīng)排序好，所以后面不可能有三個數(shù)加和等于 0粪滤，直接返回結(jié)果斧拍。
- 對于重復元素：跳過，避免出現(xiàn)重復解
- 令左指針 L=i+1杖小，右指針 R=n?1肆汹，當 L<R 時愚墓，執(zhí)行循環(huán)：
-當 nums[i]+nums[L]+nums[R]==0，執(zhí)行循環(huán)昂勉，判斷左界和右界是否和下一位置重復浪册，去除重復解。并同時將 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) : 數(shù)組排序O(nlogn); 固定指針i 循環(huán)復雜度 O(N), 雙指針遍歷O(N)
空間復雜度O(1)
18. 四數(shù)之和
對于15.三數(shù)之和 (opens new window)雙指針法就是將原本暴力O(n3)的解法，降為O(n2)的解法迫吐，四數(shù)之和的雙指針解法就是將原本暴力O(n4)的解法库菲，降為O(n3)的解法。
哈希表的經(jīng)典題目：454.四數(shù)相加II (opens new window)志膀，相對于本題簡單很多蝙昙，因為本題是要求在一個集合中找出四個數(shù)相加等于target，同時四元組不能重復梧却。而454是四個獨立的數(shù)組奇颠，只要找到A[i] + B[j] + C[k] + D[l] = 0就可以，不用考慮有重復的四個元素相加等于0的情況放航。所以可以利用hashmap存儲A[i] + B[j]之和烈拒，將之變形為O(n*n) 解法
思路：
四數(shù)之和與前面三數(shù)之和的思路幾乎是一樣的，
其實就是在三數(shù)之和的基礎上多添加一個遍歷的指針而已广鳍。
- 使用四個指針(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īng)全部求得。j++,進入下一輪循環(huán)j循環(huán)竭缝，當j循環(huán)結(jié)束后房维。 i++，進入下一輪i循環(huán)抬纸。 即(i在最外層循環(huán)咙俩，里面嵌套j循環(huán)，再嵌套雙指針left,right包夾求解)湿故。
a遍歷O(N)里嵌套b遍歷O(N)再嵌套c,d雙指針O(N)--> O(N^3)阿趁。 比暴力法O(N^4)好些吧膜蛔。
但是有一些細節(jié)需要注意，例如： 不要判斷nums[k] > target 就返回了脖阵，三數(shù)之和 可以通過 nums[i] > 0 就返回了飞几，因為 0 已經(jīng)是確定的數(shù)了，四數(shù)之和這道題目 target是任意值独撇。比如：數(shù)組是[-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;
}
}
總結(jié)：
注意三種哈希結(jié)構(gòu)的不同應用場景
數(shù)組：
242.有效的字母異位詞 (opens new window)是求 字符串a(chǎn) 和 字符串b 是否可以相互組成卵史，在383.贖金信 (opens new window)中是求字符串a(chǎn)能否組成字符串b，而不用管字符串b 能不能組成字符串a(chǎn)搜立。
使用map的空間消耗要比數(shù)組大一些以躯，因為map要維護紅黑樹或者符號表，而且還要做哈希函數(shù)的運算啄踊。所以數(shù)組更加簡單直接有效忧设！set（集合）
數(shù)組的大小是有限的，受到系統(tǒng)椀咄ǎ空間（不是數(shù)據(jù)結(jié)構(gòu)的棧）的限制址晕。
如果數(shù)組空間夠大，但哈希值比較少顿锰、特別分散谨垃、跨度非常大，使用數(shù)組就造成空間的極大浪費硼控。更適合setmap（映射） store <key, value> pair
使用用例： 1.兩數(shù)之和刘陶， 454.四數(shù)相加
使用數(shù)組和set來做哈希法的局限:
數(shù)組的大小是受限制的，而且如果元素很少牢撼，而哈希值太大會造成內(nèi)存空間的浪費匙隔。
set是一個集合，里面放的元素只能是一個key熏版，而兩數(shù)之和這道題目纷责，不僅要判斷y是否存在而且還要記錄y的下標位置，因為要返回x 和 y的下標纳决。所以set 也不能用碰逸。
map是一種<key, value>的結(jié)構(gòu)，本題可以用key保存數(shù)值阔加，用value在保存數(shù)值所在的下標。所以使用map最為合適满钟。
