每天一道LeetCode-----给定序列中2/3/4个元素的和为target的所有集合,或3个元素的和最接近target的集合
原題鏈接
2Sum
Two Sum
意思是給定一個數組,求數組中哪兩個元素的和是給定值。
蠻力法的求解就是兩層for循環,時間復雜度是O(n2)。
class Solution { public:vector<int> twoSum(vector<int>& nums, int target) {for(int i = 0; i < nums.size() - 1; ++i){for(int j = 0; j < nums.size(); ++j){if(i == j) continue;if(nums[i] + nums[j] == target)return {nums[i], nums[j]};}}} };顯然這種方式對于算法題來說復雜度過高了,仔細想一下,每次固定一個i,變化j的時候,小于i的那部分其實在之前已經訪問過一次了,為什么呢
假設nums.大小為10,此時i為5,j從0到9計算nums[i] + nums[j]
當i = 0, 1, 2, 3, 4時是不是都計算過?,所以又重復計算了一遍,整個程序多計算了n遍,這便是復雜度的原因。
解決方法,首先想到的優化就是讓j從i+1開始
class Solution { public:vector<int> twoSum(vector<int>& nums, int target) {for(int i = 0; i < nums.size() - 1; ++i){for(int j = i+1; j < nums.size(); ++j){if(nums[i] + nums[j] == target)return {nums[i], nums[j]};}}} };效率得到了一定優化,在考慮是否可以繼續優化呢,想一下,在遍歷j時
/* i == 5時遍歷了 */ nums[6], nums[7], nums[8], nums[9];/* i == 6時遍歷了 */ nums[7], nums[8] ...所以發現對于i后面的那些仍然會重復遍歷n次,還有什么方法可以優化呢,其實到這,再優化的方法只能想辦法讓復雜度變為O(n),也就是讓每一個元素只遍歷一遍,那么就不能套循環,只能使用一層循環。
for(int i = 0; i < nums.size(); ++i) {}當遍歷某個nums[i]時,唯一可能知道的、程序可能會優化的就是從nums[0]到nums[i-1],因為nums[i]往后的元素還沒有遍歷過,根本不知道是什么。再想,可不可以不判斷nums[i] + nums[j]的和而是直接判斷i前面有沒有nums[j]這個數呢?nums[j]是多少?(假設j是0到i-1中的某個數)
int left = target - nums[i];我們只需要判斷前i-1個數中有沒有left就行了,那么就需要使用某種數據結構存儲訪問過的nums[i],什么數據結構可以達到o(1)的效果呢?哈希表
/* 通常使用unordered_map來代表哈希表 */ class Solution { public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> hash;for(int i = 0; i < nums.size(); ++i){int left = target - nums[i];if(hash.find(left) != hash.end())return {hash[left], i};elsehash[nums[i]] = i;}return {0, 0};} };3Sum
擴展題型為Three Sum,原題鏈接3Sum
要求和2Sum差不多,區別在于是三個數的和,target為0,同時會有多個解,而且最要命的是竟然可以有重復的元素。
吸收了2Sum的教訓,聰明的boy可能想這里我也要用unordered_map,于是乎寫出如下代碼
class Solution { public:vector<vector<int>> threeSum(vector<int>& nums) {/* 為了處理重復元素,首先排序nums */std::sort(nums.begin(), nums.end());vector<vector<int>> ans;unordered_map<int, int> hash;for(int i = 0; i < nums.size() - 2; ++i){int target = -nums[i];hash.clear();for(int j = i + 1; j < nums.size(); ++j){int ntarget = target - nums[j];if(hash.find(ntarget) != hash.end()){ans.push_back({nums[i], nums[j], ntarget});/* * 如果后面幾個元素和當前元素重復,直接跳過,為什么可以直接跳過呢* 如果nums[j] == nums[j + 1],那么當j++后仍然求出的是當前結果,因為* ntarget只可以是在nums[j]前面的數*/while(j < nums.size() && nums[j + 1] == nums[j])++j;}elsehash[nums[j]] = j; }/* 同理 */while(i < nums.size() - 2 && nums[i] == nums[i + 1])++i;}return ans;} };于是乎興奮的submit,卻發現,額….
效率低的嚇人,為什么呢,因為即使這樣,仍然有著O(n2)的復雜度,唔…又開始進入優化的坑
對于現實主義者的我們來說O(n)是不可能了,和O(nlogn)有關的二分法好像也不太適用。首先判斷肯定是要固定一個之后再遍歷一遍,因為仍然有兩個數是不確定的。
這里引入一種方法,模仿二分發left和right的移動。因為序列是有序的,那么僅僅需要判斷nums[i + 1]和nums[nums.size() - 1]的和,從而得知是大(向左移),小(向右移動)
int left = 0; int right = nums.size() - 1; while(left < right) {if(nums[left] + nums[right] > target)--right;else if(nums[left] + nums[right] < target)++left;else{/* 結果中的一員 push到結果中*//* 防止重復 */while(left < right && nums[left] == nums[left + 1])++left;while(left < right && nums[right] == nums[right - 1])--right;/* * 為什么這里需要++和--* 此時left是最后一個和之前的nums[left]重復的下標,需要++到第一個不重復的下標* 因為nums[left]已經改變,nums[left] + nums[right]不可能再等于target,所以right無需保持在最后一個和之前nums[right]重復的位置,也向前移動--* /++left;--right;} }利用這種方法的效率比上面高一些,可能原因就在于是從兩邊同時向中間移動,但是仍然擺脫不了O(n3)的復雜度(我一直以為上面的方法可以達到O(logn)….錯了好久),代碼如下
class Solution { public:vector<vector<int>> threeSum(vector<int>& nums) {std::sort(nums.begin(), nums.end());vector<vector<int>> ans;for(int i = 0; i < nums.size(); ++i){int target = -nums[i];int left = i + 1;int right = nums.size() - 1;while(left < right){if(nums[left] + nums[right] > target)--right;else if(nums[left] + nums[right] < target)++left;else{ans.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;--right;}}while(i < nums.size() - 2 && nums[i] == nums[i + 1])++i;}return ans;} };此時可能回想,2Sum我能不能也使用這種方法提高效率呢,想法是好的,可是要求是有序數組,而基于比較的最快的排序快排也只能是O(nlogn),顯然得不償失
4Sum
最后一個擴展為4Sum,原題鏈接4Sum
和3Sum完全一樣,只是4個數的和,代碼也類似,不再強調了。
唔…leetcode上的解法也都是O(n3),既然都這樣就不想優化了
3Sum Closest
原題鏈接3Sum Closest
意思是給定一個數組,求數組中哪三個數的和最接近target,返回三個數的和。
這道題和3Sum是一樣的,利用上面的思想,固定一個,剩下兩個從兩邊開始找即可,當然需要排好序,代碼如下
注:多數代碼都在這里直接手打的,難免有錯誤,輕噴
總結
以上是生活随笔為你收集整理的每天一道LeetCode-----给定序列中2/3/4个元素的和为target的所有集合,或3个元素的和最接近target的集合的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: libevent源码学习-----eve
- 下一篇: 每天一道LeetCode-----字符串