1. 首頁 > 生活百科 > >

【算法訓練營day7】LeetCode454. 四數相加II LeetCode383. 贖金信 LeetCode15. 三數之和 LeetCode18. 四數之和

生活百科

【算法訓練營day7】LeetCode454. 四數相加II LeetCode383. 贖金信 LeetCode15. 三數之和 LeetCode18. 四數之和LeetCode454. 四數相加II題目鏈接：454. 四數相加II
初次嘗試沒有思路，對于map的使用還不是非常熟練 ， 正好借這幾個題多練習一下 。
看完代碼隨想錄后的想法四個數組兩兩一組，寫成兩個嵌套的for循環 ， 這樣可以保證時間復雜度最小 ， 其中使用map的原因是不僅要統計前兩個數組的元素和 ， 還要統計每個和出現的次數 。
class Solution {public:int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {unordered_map<int, int> hashMap;int count = 0;for (int i = 0; i < nums1.size(); i++) {for (int j = 0; j < nums2.size(); j++) {auto iter = hashMap.find(nums1[i] + nums2[j]);if (iter != hashMap.end()) {iter -> second++;}else {hashMap.insert(pair<int, int>(nums1[i] + nums2[j], 1));}}}for (int i = 0; i < nums3.size(); i++) {for (int j = 0; j < nums4.size(); j++) {auto iter = hashMap.find(0 - nums3[i] - nums4[j]);if (iter != hashMap.end()) {count += iter -> second;}}}return count;}};LeetCode383. 贖金信題目鏈接：383. 贖金信
初次嘗試感覺和242. 有效的字母異位詞是一個思路的題，解起來不難，一遍ac 。
class Solution {public:bool canConstruct(string ransomNote, string magazine) {vector<int> hashVec(26, 0);for (int i = 0; i < magazine.size(); i++) {hashVec[magazine[i] - 'a']++;}for (int i = 0; i < ransomNote.size(); i++) {hashVec[ransomNote[i] - 'a']--;if (hashVec[ransomNote[i] - 'a'] < 0) {return false;}}return true;}};看完代碼隨想錄后的想法思路一樣 。
LeetCode15. 三數之和題目鏈接：15. 三數之和
初次嘗試思路比較混亂，沒有想到解法 。
看完代碼隨想錄后的想法這題應該是刷題刷到現在，思考量最大的一道題了，很容易想著想著陷入疑惑，最好邊畫圖邊想 。這里按照思考順序列舉幾個解題的關鍵點：

  1. 為什么上來要先排序？LeetCode官方題解中對此有非常清楚的解釋 。
    「不重復」的本質是什么？我們保持三重循環的大框架不變 ， 只需要保證：
    第二重循環枚舉到的元素不小于當前第一重循環枚舉到的元素；
    第三重循環枚舉到的元素不小于當前第二重循環枚舉到的元素 。
    也就是說，我們枚舉的三元組 (a, b, c) 滿足a≤b≤c，保證了只有 (a, b, c)這個順序會被枚舉到，而 (b, a, c)、(c, b, a) 等等這些不會，這樣就減少了重復 。要實現這一點，我們可以將數組中的元素從小到大進行排序 ， 隨后使用普通的三重循環就可以滿足上面的要求 。
  2. 但是僅僅排序之后就可以保證輸出的三元組不重復了嗎？不一定，排序過后的數組仍然可能存在連續相等的元素，這可能會導致在遍歷過程中，連續幾個循環a取得相同的值，導致輸出重復的三元組，b和c同理，所以仍然需要對abc去重 。
  3. 但是對于a和bc的去重方式又有所差別，對于b和c，我們可以在left和right指針指向的下一個元素和現在指向的元素相等的時候 ， 直接跳過下一個元素；而對于a ， 我們需要考慮特殊的情況，比如遇到{0, 0, 0}或者{-1, -1, 2}這樣的輸入時，如果使用nums[i] == nums[i + 1]這樣的判斷，就會漏掉(0, 0, 0)或者(-1, -1, 2)這樣的三元組，所以對于a，應該使用nums[i] == nums[i - 1]這樣的判斷，這樣才能保證既不漏掉特殊情況，又不輸出因為a重復而重復的三元組 。
class Solution {public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> ans;sort(nums.begin(), nums.end());for (int i = 0; i < nums.size(); i++) {if (nums[i] > 0) {return ans;}// 對a去重if (i > 0 && nums[i] == nums[i - 1]) {continue;}int left = i + 1, right = nums.size() - 1;while (left < right) {if (nums[i] + nums[left] + nums[right] < 0) {left++;}else if (nums[i] + nums[left] + nums[right] > 0) {right--;}else {ans.push_back(vector<int>{nums[i], nums[left], nums[right]});// 對b和c去重while (left < right && nums[left] == nums[left + 1]) left++;while (left < right && nums[right] == nums[right - 1]) right--;left++;right--;}}}return ans;}};LeetCode18. 四數之和題目鏈接：18. 四數之和
初次嘗試【【算法訓練營day7】LeetCode454. 四數相加II LeetCode383. 贖金信 LeetCode15. 三數之和 LeetCode18. 四數之和】算是三數之和的拓展題，本質上就是在三數之和的基礎上再加一層for循環，但是在實際寫的過程中有幾個細節需要注意 。

推薦閱讀