多站点wordpress安装,免费saascrm,网络实施方案,怎样做网络推广佳选豪升网络好链接
一般这种三数之和#xff0c;四数之和都使用双指针#xff0c;复杂度最优#xff0c;次一级可使用哈希表。前者要求有序#xff0c;后者空间上有花费。
题目#xff1a;
题目要求答案中不能出现重复vector#xff0c;比如{-1 1 0}和{-1 0 1}#xff1b;
这两个…链接
一般这种三数之和四数之和都使用双指针复杂度最优次一级可使用哈希表。前者要求有序后者空间上有花费。
题目
题目要求答案中不能出现重复vector比如{-1 1 0}和{-1 0 1}
这两个在固定住i 指向0位置然后在后续子数组中查找合适的j 和k 时会出现重复所以我们对数组排序通过if语句解决重复问题。
我们要找nums[i]num[j]nums[k]0乍一看需要三个指针三种循环来判断但这显然是不合适的于是我们固定住i也就是让i从开头遍历到结尾即可然后让j 从i 后面开始k从最后一个元素开始往中间遍历。
如果刚开始也就是图中这个位置三个相加都小于0那么就不存在答案因为我们的数组是有序的k越往做越小了。
所以我们只需要找三个相加大于等于0的这样越往前越有可能找到0的情况。
为什么要一直往前呢万一出现下图这样k指向的值刚好就可以和nums[i] nums[j]相加为0为何还要往前 因为我们怕重复{-2 0 2}{-2 0 2}{-2 0 2}{-2 0 2}...........这不符合题目要求所以我们尽量往左走只留一个就行了。
另外代码中其实还有可以优化的地方
也就是这两点因为排序后并不能去重所以会出现
i指向这两个位置找到的答案还是会重复所以我们在i 至少找过一次也就是i0即 i时且nums[i]nums[i-1]时continue住不要往下循环了别找了答案如果有都是一样的没必要循环了。
还有j 的情况也是如此ji1也就是j 在当前i 这个位置至少已经找过一次了如果j 往后挪了还是相等那也不用找了。
class Solution {
public:vectorvectorint threeSum(vectorint nums) {vectorvectorint res;sort(nums.begin(), nums.end());for (int i 0; i nums.size(); i) {if (i nums[i] nums[i - 1]) // if (i 1 nums.size() // nums[i] nums[i 1])continue;for (int j i 1, k nums.size() - 1; j k; j) {if (j i 1 nums[j] nums[j - 1]) // if (j 1 nums.size() // nums[j] nums[j 1])continue;while (k - 1 j nums[j] nums[k - 1] nums[i] 0)--k;if (nums[i] nums[j] nums[k] 0) {res.push_back({nums[i], nums[j], nums[k]});}}}return res;}
};
