454.四數相加II

文檔講解：代碼隨想錄算法訓練營
視頻講解：算法視頻公開課
狀態：思路自己想出來了，但代碼沒有實現出來

解題思路

首先如果使用暴力方法，也就是對數組nums1到nums2依次遍歷，直到找到符合要求的組合，那么時間復雜度為O(n^4)。
如何能減少時間復雜度呢？
想到之間 242.有效字母異位詞 的解法，我們可以遍歷nums1和nums2，求出二者num1 + num2之和的組合，并記錄出現的次數。
接著，我們再遍歷nums3和nums4，現在我們的目標值是找到target = 0 - num3 - num4，因為題目要求num1 + num2 + num3 + num4 = 0，也就是要找num1 + num2 = - (num3 + num4)。然后在map里找target是否出現過，如果出現過，計數的變量count要加上target在map里的value值，即target在map里存儲的次數。
代碼實現：

class Solution {
public:int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {unordered_map<int,int> map;// 遍歷 nums1 和 nums2for (int num1 : nums1) {for (int num2 : nums2) {map[num1 + num2] ++;}}int count = 0;// 遍歷 nums3 和 nums4for (int num3 : nums3) {for (int num4 : nums4) {int target = 0 - num3 - num4;if (map.find(target) != map.end()) {count += map[target];}}}return count;}
};

383.贖金信

文檔講解：代碼隨想錄算法訓練營
狀態：自己完全做出來了

自己解答：

class Solution {
public:bool canConstruct(string ransomNote, string magazine) {unordered_map<int,int> map;// 遍歷 magazine 字符串for (int i = 0; i < magazine.size(); i++) {map[magazine[i] - 'a'] ++;}// 遍歷 ransomNote 字符串for (int i = 0; i < ransomNote.size(); i++) {map[ransomNote[i] - 'a'] --;}// 是否有 value < 0，如果有就不能構成for (int i = 0; i < 26; i++) {if (map[i] < 0) return false; }return true;}
};

代碼隨想錄講解

暴力做法

class Solution {
public:bool canConstruct(string ransomNote, string magazine) {// 遍歷 magazine 和 ransomNotefor (int i = 0; i < magazine.size(); i++) {for (int j = 0; j < ransomNote.size(); j++) {// 如果找到相同字符，就把這個字符從 ransomNote里刪除if (magazine[i] == ransomNote[j]) {ransomNote.erase(ransomNote.begin() + j);}}}// 如果 ransomNote 里還有字符，那么就不構成if (ransomNote.length() != 0) return false;return true;}
};

哈希表

題目說只有小寫字母，采用空間換取時間的哈希策略，用一個長度為26的數組來記錄magazine出現字母的次數。
為什么不采用map呢，因為map要維護紅黑樹或者哈希表，而且還要做哈希函數，是費時的！數據量大的話就能體現出來差別了。 所以數組更加簡單直接有效！

class Solution {
public:bool canConstruct(string ransomNote, string magazine) {int hash[26] = {};for (int i = 0; i < magazine.size(); i++) {hash[magazine[i] - 'a'] ++;}for (int i = 0; i < ransomNote.size(); i++) {hash[ransomNote[i] - 'a'] --;}for (int i = 0; i < 26; i++) {if (hash[i] < 0) return false;}return true;}
};

15.三數之和

文檔講解：代碼隨想錄算法訓練營
視頻講解：算法視頻公開課
狀態：自己有思路，在代碼隨想錄基礎上做優化

雙指針

這道題要使用哈希表的話，在去重操作中可能非常復雜，很難寫全。
這道題應該使用雙指針法。
步驟一：先對數組進行從小到大排序；
步驟二：遍歷數組，注意我們只需要遍歷到數組的倒數第三個位置即可，因為我們需要 left 和 right，并且 i < left < right；
步驟三：去重。如果第一個數大于0即 nums[i] > 0，那么直接返回即可，不可能再有答案了。如果循環中，這個元素和上一個元素數值相等，那么直接跳過。
注意：我的語言描述是，這個元素和上一個元素數值相等，不是這個元素和下一個元素數值相等。這是有區別的，比如nums = [-1, -1, 0, 1, 2]，當 i = 0 的時候，此時指向第一個 -1，如果判斷這個元素與下一個元素，即 i = 1 的時候，此時指向的數也為 -1，那么就應該跳過 i = 0，明顯是不正確的。正確應該是==該元素與上一個元素的值相等，跳過該元素。
步驟三：設 left = i + 1, right = n - 1，開始循環，循環條件是left < right，注意這里不能加上=，當想到等時候就應該終止循環，而不是接著循環。
步驟四：當三數之和 > 0，那么讓 right --；如果三數之和 < 0，那么就讓 left ++；如果三數之和 = 0，就把結果放入到答案數組res中。
步驟五：放入res后，需要對left 和 right去重，如果 left < right，這個是前提，也必須在循環條件里，不寫的話，可能造成死循環，比如數組nums = [0, 0, 0, 0, 0]，就會一直循環到頭。對于right，如果下一個元素和該元素相等，那么就跳過元素；對于left，如果下一個元素和該元素相等，就跳過元素。
步驟六：找到符合要求的一組時，要讓left 和 right收縮

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> res;int n = nums.size();// 對數組 nums 進行從小到大排序sort(nums.begin(), nums.end());for (int i = 0; i < n - 2; i ++) {if (nums[i] > 0) return res;if (i > 0 && nums[i] == nums[i - 1]) continue;int left = i + 1;int right = n - 1;while (left < right) {if (nums[i] + nums[left] + nums[right] > 0) right --;else if (nums[i] + nums[left] + nums[right] < 0) left ++;else {res.push_back({nums[i], nums[left], nums[right]});while (left < right && nums[left] == nums[left + 1]) left ++;while (left < right && nums[right] == nums[right - 1]) right --;// 找到解，收縮left 和 rightleft ++;right --;}}}return res;}
};

優化改進

可以加上幾個判斷：
如果nums的前三個元素之和 > 0，那么不可能再有解，直接break；
如果nums的后兩個元素 + nums[i] < 0 ，那么可以跳過本次循環，left 和 right無論怎么移動也不能得到答案。
注意寫i + 1，i + 2，for循環中一定寫的是i < n - 2，否則會造成越界訪問

			if (nums[i] + nums[i + 1] + nums[i + 2] > 0) break;if (nums[i] + nums[n - 2] + nums[n - 1] < 0) continue;

除此之外，在找到答案的時候，對left 和 right的處理還可以再優化，代碼更簡潔，更易理解。
每次找到答案，我們先對left 和 right進行收縮操作，然后進行判重，也就是如果left < right，對于left，就是，該元素與上一個元素相等，就跳過，和步驟三一致。

		for (left ++; left < right && nums[left] == nums[left - 1]; left ++);for (right --; left < right && nums[right] == nums[right + 1]; right --);

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> res;int n = nums.size();sort(nums.begin(), nums.end());for (int i = 0; i < n - 2; i ++) {if (nums[i] > 0) return res;if (nums[i] + nums[i + 1] + nums[i + 2] > 0) break;if (nums[i] + nums[n - 2] + nums[n - 1] < 0) continue;if (i > 0 && nums[i] == nums[i - 1]) continue;int l = i + 1, r = n - 1;while (l < r) {if (nums[i] + nums[l] + nums[r] > 0) r --;else if (nums[i] + nums[l] + nums[r] < 0) l ++;else {res.push_back({nums[i], nums[l], nums[r]});for (l ++; l < r && nums[l] == nums[l - 1]; l ++);for (r --; l < r && nums[r] == nums[r + 1]; r --);}}}return res;}
};

18.四數之和

文檔講解：代碼隨想錄算法訓練營
視頻講解：算法視頻公開課
狀態：自己仿照三數之和做出來了，調試了好幾次，int換成long long，剪枝的位置不正確等等，最后還是AC了

自己的解答

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> res;sort (nums.begin(), nums.end());int n = nums.size();for (int i = 0; i < n - 3; i ++) {if (i > 0 && nums[i] == nums[i - 1]) continue;if ((long long)nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break;if ((long long)nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target) continue;for (int j = i + 1; j < n - 2; j ++) {if (j > i + 1 && nums[j] == nums[j - 1]) continue;int l = j + 1, r = n - 1;while (l < r) {if ((long long)nums[i] + nums[j] + nums[l] + nums[r] > target) r --;else if ((long long)nums[i] + nums[j] + nums[l] + nums[r] < target) l ++;else {res.push_back({nums[i], nums[j], nums[l], nums[r]});for (l ++; l < r && nums[l] == nums[l - 1]; l ++);for (r --; l < r && nums[r] == nums[r + 1]; r --);}} }}return res;}
};

系統講解

本題和三數之和非常像，整體思路就是在三數之和的循環外，再套上一層循環即可。
這里要注意剪枝和去重。
首先對于一級剪枝操作，這里不能直接寫nums[i] > target，直接就break 這是錯誤的，如果target < 0，num[i] < 0，負數加負數會變的越來越小，還是可能有解的，所以我們要加上條件。對于剪枝，同理還有如果前四個數之和 > target，直接break；nums[i]加上后三個數 < target，continue，注意，這里要轉成long long類型才能過。
對于去重，和之前同理。

	// 一級剪枝操作if (nums[i] > target && nums[i] > 0 && target > 0) break;if ((long long)nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break;if ((long long)nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target) continue;// 一級去重if (i > 0 && nums[i] == nums[i - 1]) continue;

二級去重，就仿照一級去重來寫，把nums[i] + nums[j]當成一個整體。

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> res;int n = nums.size();sort(nums.begin(), nums.end());for (int i = 0; i < n - 3; i ++) {// 一級剪枝，注意 long longif (nums[i] > target && nums[i] > 0 && target > 0) break;if ((long long)nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break;if ((long long)nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target) continue;// 一級去重if (i > 0 && nums[i] == nums[i - 1]) continue;for (int j = i + 1; j < n - 2; j++) {// 二級剪枝if (nums[i] + nums[j] > target && nums[i] + nums[j] > 0 && target > 0) break;if ((long long)nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) break;if ((long long)nums[i] + nums[j] + nums[n - 2] + nums[n - 1] < target) continue;// 二級去重if (j > i + 1 && nums[j] == nums[j - 1]) continue;// 下面同三數之和邏輯int l = j + 1, r = n - 1;while (l < r) {if ((long long)nums[i] + nums[j] + nums[l] + nums[r] > target) r --;else if ((long long)nums[i] + nums[j] + nums[l] + nums[r] < target) l ++;else {res.push_back({nums[i], nums[j], nums[l], nums[r]});for (l ++; l < r && nums[l] == nums[l - 1]; l ++);for (r --; l < r && nums[r] == nums[r + 1]; r --);}}}}return res;}
};