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！了！哈！哈！哈！
退役了再见
