今日做一道很常规的算法题，从数组中找出三个数和为0，用简单的“三个指针”实现，却踩了一个非常愚蠢的坑。。。
bug出现
- 思路：先排序，然后i、j、k有序查找
- 报错：非法访问内存
- 错误代码：
/* 3 pointers */
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> res;
for (int i = 0; i < nums.size() - 2; i++) {
if (i > 0 && nums[i] == nums[i-1]) {
continue; // exclude duplicates
}
int j = i + 1, k = nums.size() - 1;
while (j < k) {
if (nums[i] + nums[j] + nums[k] < 0) {
j++;
} else if (nums[i] + nums[j] + nums[k] > 0) {
k--;
} else {
res.push_back(vector<int>{nums[i], nums[j], nums[k]});
j++;
while (j < k && nums[j] == nums[j-1]) {
j++; // exclude duplicates
}
k--;
while (j < k && nums[k] == nums[k+1]) {
k--; // exclude duplicates
}
}
}
}
return res;
}
};
分析
上面代码的bug在哪里？（题目要求无序三元组不能重复，于是做了一些去重处理，但这并不是问题的关键）我真的找了好久。。。
后来发现在输入向量的长度为0或1时才会报这个内存有关的错误，于是定位到了最外层for循环的这一行：
for (int i = 0; i < nums.size() - 2; i++)
由于循环变量i是第一个数的下标，而一共有三个数，我便将循环条件设为了i < nums.size() - 2，问题就出在这里：
nums.size()是unsigned int类型，如果它是0或1，那么减去2之后就变成了一个很大的无符号数（正数）。于是循环里面肯定就有非法内存被访问、被使用。
解决
如果用IDE写代码，会报出一个int类型的i与unsigned int类型的nums.size()不匹配的警告，然而我以前却常常无视它。。。
注意如果这样写成下面这样，虽然类型一致了，但是bug还在：
for (unsigned int i = 0; i < nums.size() - 2; i++)
所以解决这个问题，如果不改变代码逻辑，就要用强制类型转换：
for (int i = 0; i < (int)nums.size() - 2; i++)
至此，bug排除，这个故事告诉我们：
- 不要无视warning
- 隐式类型转换要慎用
