LeetCode错误:AddressSanitizer: heap-buffer-overflow on address...............(3sum)
一下午的时间都填在了这个bug上,比较了别人的代码,明明核心部分都是一样的思路,为啥我的就是过不去,把别人的粘贴过来就可以过......知道是缓冲区溢出,可能是数组访问越界,然后百般检查了vector没问题呀?后来一点点比较我的代码和别人的代码,一个个细微的地方去比较,怎么也想不到最后问题出在一个if判断的语句中,数组访问越界了。
我没有想到这个做与运算的地方要先判断back>0,确保back>0后,才能在数组中访问下标为back-1的元素,要是不先判断back>0,很可能访问越界。
这算是基础错误,怪自己练习太少,对BUG不敏感,跪着接自己的锅。
The name of this Q is 3Sum , as follows .
看了大部分代码的思路都是:
1.先用sort函数做排序,时间复杂度是nlogn;
2.再一个大for循环,从数组的第一个元素开始遍历;for循环中用两个标记,front,back,front 指向i+1,back指向最后一个元素,然后两头向中间靠拢,当两个标记指的元素值加上下标为i的值,结果为0时,为一组输出结果。
3.注意题目要求不能有重复的完全相同的一组结果,当然每组结果中可以有值相等的元素。这个时候需要做一些小处理,遍历到下标为k的元素时,若a[k[==a[k+1]就可以直接k++往后跳过了。
4.整个代码复杂度是n*n.
源代码:
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
sort(nums.begin(),nums.end());
if(nums.size()<3)
return result;
for(int i=0;i<nums.size();i++)
{
int front=i+1;
int back=nums.size()-1;
int target=-nums[i];
while(front<back)
{
if(nums[i]>0)
break;
if(nums[front]+nums[back]<target)
{
front++;
continue;
}
else if(nums[front]+nums[back]>target)
{
back--;
continue;
}
else{
vector<int> re;
re.push_back(nums[i]);
re.push_back(nums[front]);
re.push_back(nums[back]);
result.push_back(re);
while(nums[front]==nums[front+1]&&front+1<nums.size()-1)
front++;
while(back>0&&nums[back]==nums[back-1])
back--;
front++;
back--;
}
}
while(i+1<nums.size()-1&&nums[i]==nums[i+1])
i++;
}
return result;
}
};
代码写得不精简,参考很多,如下:
https://leetcode.com/problems/3sum/discuss/277991/C%2B%2B-O(N2)-solution-w-comments
https://leetcode.com/problems/3sum/discuss/277862/c%2B%2B-o(n2)-solution