sort函數居然能改變元素值？記一次有趣的Bug——四數之和
坐標leetcode:
我想都不想直接深度優先搜索暴力求解：
class Solution { public: vector<vector<int>> res; //答案 int sum =0; //temp中的總和 vector<int> temp;//用於存儲一個解 bool check(vector<int>&a,vector<int> &b)//用於判斷兩個解是否相同(因為res中已經排序所以直接比較 很方便) { for(int i = 0;i<4;i++) { if(a[i]!=b[i]) return false; } return true; } void dfs(vector<int>&nums,int sub,int target)//sub為當前下標 { if(temp.size()==4) { if(sum == target) { for(int i =0;i<res.size();++i) //判斷重複 若重複則不加入此解 { if(check(res[i],temp)) return; } sort(temp.begin(),temp.end()); res.push_back(temp); } return; } if(sub>=nums.size()) return ; //存入當前下標的元素 sum+=nums[sub]; temp.push_back(nums[sub]); dfs(nums,sub+1,target); //不存入當前下標的元素 sum-=nums[sub]; temp.erase(temp.end()-1); dfs(nums,sub+1,target); } vector<vector<int>> fourSum(vector<int>& nums, int target) { dfs(nums,0,target); return res; } };
我自信地按下了提交按鈕，結果連示例都沒過得了！！？
而且結果很讓人問號：
這···怎麼會出現[-2,-1,-1,2]這個解？？
於是我把sort注釋掉 把判重也注釋掉：
class Solution { public: vector<vector<int>> res; //答案 int sum =0; //temp中的總和 vector<int> temp;//用於存儲一個解 bool check(vector<int>&a,vector<int> &b)//用於判斷兩個解是否相同(因為res中已經排序所以直接比較 很方便) { for(int i = 0;i<4;i++) { if(a[i]!=b[i]) return false; } return true; } void dfs(vector<int>&nums,int sub,int target)//sub為當前下標 { if(temp.size()==4) { if(sum == target) {
//sort(temp.begin(),temp.end());
//for(int i =0;i<res.size();++i) //判斷重複 若重複則不加入此解 //{ // if(check(res[i],temp)) // return; // } res.push_back(temp); } return; } if(sub>=nums.size()) return ; //存入當前下標的元素 sum+=nums[sub]; temp.push_back(nums[sub]); dfs(nums,sub+1,target); //不存入當前下標的元素 sum-=nums[sub]; temp.erase(temp.end()-1); dfs(nums,sub+1,target); } vector<vector<int>> fourSum(vector<int>& nums, int target) { dfs(nums,0,target); return res; } };
好的，結果驚了，就是正確答案：
於是我開vs復原了這題的解，同樣是這個奇怪的結果。
這···難道sort改變了元素值的大小？？？
然後我單獨試驗了sort函數，發現函數並沒有問題。
那麼問題來了。。。。。。Bug出在哪裡？為什麼會出現sort函數改變了元素值的假象？
於是我開始了不同的嘗試探索問題的原因。
一、改變記錄sum的方法
我將全局變數sum去掉，改為需要的時候當場對temp求和。
按道理，結果應該不會改變，但是卻改變了。[-2,-1,-1,2]這個解變為了[-1,-1,0,2]。
這說明dfs的執行邏輯出現了問題。
二、用大腦運行程式
這果然是個好辦法！。。。
我從頭到尾思考了很多遍，感覺邏輯沒問題啊。
於是我又從頭到尾思考了很多遍，
終 於 知 道 bug 到 底 在 哪 里 了 ！
這一切都是因為全局變數temp！
我以為temp.erase(temp.end()-1)就能夠把剛才加入的元素給彈掉。。
結果並不是！！因為temp已經排序過了！！！最後一個元素不是在這個遞歸層加進去的那個元素！！！
vector<int> ttemp = temp; sort(ttemp.begin(), ttemp.end());
for(int i =0;i<res.size();++i)
{
if(check(res[i],ttemp))
return;
}
res.push_back(ttemp);
哈！哈！哈！這樣總算能過吧！這程式碼已經絕！對！不！會！有！b！u！g！了！哈！哈！哈！
退役了再見
