454.四數(shù)相加

題目鏈接：454. 四數(shù)相加 II - 力扣（LeetCode）

視頻/文檔鏈接：代碼隨想錄 (programmercarl.com)

第一想法

遍歷數(shù)組num1,num2，計(jì)算其和出現(xiàn)的數(shù)量，放入map集合中，鍵為和，值為出現(xiàn)的次數(shù)。遍歷num3，num4,0-若其和的值出現(xiàn)在Map集合中，則count+=該值即可。

可優(yōu)化點(diǎn)

不熟悉調(diào)用mapAPI。

map.put(sum, map.getOrDefault(sum, 0) + 1);
res += map.getOrDefault(0 - i - j, 0);

代碼

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

383.贖金信

?題目鏈接：383. 贖金信 - 力扣（LeetCode）

視頻/文檔鏈接：代碼隨想錄 (programmercarl.com)

第一想法

這個(gè)題和力扣242題很像。

對(duì)于案例：ransomNote = "aa", magazine = "aab"

力扣242：字符串s和t每個(gè)字母出現(xiàn)的次數(shù)都必須一樣。所以返回false

力扣383：只要求ransdomNote每個(gè)字母數(shù)量<=magazine，則返回true。

代碼

一次過(guò)。

class Solution {public boolean canConstruct(String ransomNote, String magazine) {int[] ransdomArr = new int[26];int[] magazineArr = new int[26];for (int i = 0; i < ransomNote.length(); i++) {ransdomArr[ransomNote.charAt(i)-'a']++;}for (int j = 0; j < magazine.length(); j++) {magazineArr[magazine.charAt(j)-'a']++;}for (int i = 0; i < 26; i++) {if(ransdomArr[i]>magazineArr[i])return false;}return true;}
}

15.三數(shù)之和

題目鏈接：15. 三數(shù)之和 - 力扣（LeetCode）

文檔/視頻鏈接：代碼隨想錄 (programmercarl.com)

第一想法

a+b+c = 0,直接暴力循環(huán)然后去重。
a從第1個(gè)元素遍歷，b從i+1處遍歷，然后c的值應(yīng)為-（a+b）,看map集合中是否存在。最終去除重復(fù)元素。

代碼隨想錄想法

首先先將數(shù)組排序，一層for循環(huán)，i代表當(dāng)前元素a，再定義left指針b和right指針c，

若相加之和>0,則right--，相加之和<0,left++，相加之和 = 0，則加入結(jié)果集。直到left = right終止循環(huán)，相等時(shí)無(wú)意義。

當(dāng)去重a時(shí)需要判斷 if(nums[i] != nums[i-1])，即當(dāng)前元素與之前元素不同，那么第一個(gè)元素不是會(huì)報(bào)空指針異常么，怎么避免這個(gè)問(wèn)題？按照這樣就能避免對(duì) i= 0 時(shí)進(jìn)行判定了。

  if (i > 0 && nums[i] == nums[i - 1]) {  // 去重acontinue;}

每次遍歷對(duì)第一個(gè)元素要都判斷是否>0，所以nums[i]>0這個(gè)判斷邏輯要加到循環(huán)里面。還有個(gè)細(xì)節(jié)是直接return，而不是continue了。因?yàn)橐呀?jīng)排序的數(shù)組，一旦碰上正數(shù)，往后的也必須是正數(shù)。

關(guān)于b和c的去重

我在看視頻的時(shí)候也想的是直接將去重邏輯提前。

?if (nums[i] + nums[left] + nums[right] > 0) {
? ? ? ? right--;
? ? ? ? // 去重 right
? ? ? ? while (left < right && nums[right] == nums[right + 1]) right--;
? ? } else if (nums[i] + nums[left] + nums[right] < 0) {
? ? ? ? left++;
? ? ? ? // 去重 left
? ? ? ? while (left < right && nums[left] == nums[left - 1]) left++;
? ? } else {
? ? }

但對(duì)提升效率沒(méi)有幫助，反正去重也是一個(gè)一個(gè)減下去，在哪里減都是一樣的。

索性放在else中，結(jié)構(gòu)更好看一點(diǎn)。

同時(shí)去重時(shí)還要判斷l(xiāng)eft<right，是為了防止指針越界需要加上?？梢杂浶∧０婢褪莣hile（left<right）再套while循環(huán)，里面while條件要考慮加外層循環(huán)條件。

代碼

class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> endResult = new ArrayList<>();Arrays.sort(nums);//排序for (int i = 0; i < nums.length; i++) {if(nums[i]>0)return endResult;if(i>0&&nums[i]==nums[i-1])continue;//進(jìn)入判斷邏輯int left = i + 1;int right = nums.length - 1;while (left < right){if(nums[i]+nums[left]+nums[right]>0)right--;else if(nums[i]+nums[left]+nums[right]<0)left++;else{//將結(jié)果加入endResult中,這個(gè)語(yǔ)句是這樣寫(xiě)的。endResult.add(Arrays.asList(nums[i],nums[left],nums[right]));//這里就需要去重了while (left<right&&nums[right-1]==nums[right])right--;//假設(shè)2，3，3,循環(huán)結(jié)束后right指的是最后一個(gè)重復(fù)元素3(第2個(gè))while (left<right&&nums[left+1]==nums[left])left++;//同理right--;//這里才正真跳到最終不同的值上left++;}}}return endResult;}
}

18.四數(shù)之和

題目鏈接/文章講解/視頻講解： 代碼隨想錄

在三數(shù)之和基礎(chǔ)上再套一層循環(huán)。

看完代碼隨想錄的想法

剪枝的邏輯不能是nums[i]>0，因?yàn)榇藭r(shí)目標(biāo)是target，而target可能是負(fù)數(shù)，排序之后的數(shù)組可以是越加越小，即target = -5， nums = [-4,-1,0,0]。

但是我們依舊可以去做剪枝，邏輯變成nums[i] > target && (nums[i] >=0 || target >= 0)就可以了。

?每次對(duì)第一個(gè)元素不做判斷，所以第二層循環(huán)去重時(shí)j>i+1&&nums[j]==nums[j-1],而不應(yīng)當(dāng)慣性思維是j>0

class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>> endResult = new ArrayList<>();Arrays.sort(nums);for (int i = 0; i < nums.length; i++) {//剪枝if(nums[i]>target&&(nums[i]>0||target>0))return endResult;if(i>0&&nums[i]==nums[i-1])continue;for (int j = i + 1; j < nums.length - 1 - 1; j++) { //0,1,2,3，j<2,//去重if( j > i+1 &&nums[j] == nums [j-1]) //j為1時(shí)不應(yīng)去重continue;int left = j+1;int right = nums.length-1;while (left<right){if(nums[i]+nums[j]+nums[left]+nums[right]>target)right--;else if(nums[i]+nums[j]+nums[left]+nums[right]<target)left++;else{endResult.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));while (left<right&&nums[right-1] ==nums[right])right--;while (left<right&&nums[left+1] == nums[left])left++;right--;left++;}}}}return endResult;}
}