网站建设成都哪家公司好,同城信息小程序源码,深圳网站开发教程,怎么做网站程序题目
给你一个整数数组 nums #xff0c;判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k #xff0c;同时还满足 nums[i] nums[j] nums[k] 0 。请你返回所有和为 0 且不重复的三元组。 注意#xff1a;答案中不可以包含重复的三元组。 示例…题目
给你一个整数数组 nums 判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k 同时还满足 nums[i] nums[j] nums[k] 0 。请你返回所有和为 0 且不重复的三元组。 注意答案中不可以包含重复的三元组。 示例 1 输入nums [-1,0,1,2,-1,-4] 输出[[-1,-1,2],[-1,0,1]] 解释 nums[0] nums[1] nums[2] (-1) 0 1 0 。 nums[1] nums[2] nums[4] 0 1 (-1) 0 。 nums[0] nums[3] nums[4] (-1) 2 (-1) 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意输出的顺序和三元组的顺序并不重要。 示例 2 输入nums [0,1,1] 输出[] 解释唯一可能的三元组和不为 0 。 示例 3 输入nums [0,0,0] 输出[[0,0,0]] 解释唯一可能的三元组和为 0 。 提示 3 nums.length 3000 -105 nums[i] 105
解析
本题如果采用暴力的方式使用三重for循环来解题的话最后的时间复杂度为o(n3) 在这里如果采用哈希法来解决的话在剪枝和去重的过程中比较复杂但是如果采用双指针配合一定的思路来解题的话在剪枝和去重的过程中会稍微简单一点 循环遍历i然后通过左右指针左指针为i的下一位右指针为最右边然后直接计算三数之和如果之和大于0最right–,如果之和小于0则left 知道等于0之后执行剪枝才不会返回两个一模一样的数组 这里去重的思路对于i来说就是i从第二个位置开始不可以和前面一个相同array[i]!array[i-1]比如[-1,-1,0,1,2,3,4],这样一个数组的话循环到数组的下标为1的时候就要直接进行下一次循环对于left和right也是一样,只有简单的区别就是left是和他的前一位比较但是right是和后以为比较同时还应该在while循环中
代码
class Solution {
public:vectorvectorint threeSum(vectorint nums) {vectorvectorint res;sort(nums.begin(),nums.end()); // 使用双指针的方式来解题for(int i0;inums.size();i){if(nums[i]0) return res;if(i0nums[i]nums[i-1]) continue;int lefti1;int rightnums.size()-1; // 题目要求的是求三数之和,如果两个数相等的话直接达不到要求while(rightleft){int sumnums[i]nums[left]nums[right];// 使用这种结构的时候需要注意的最后用到else,所以需要使用if,else if else来做逻辑结构if(sum0) right--;else if(sum0) left;else{res.push_back(vectorint{nums[i],nums[left],nums[right]});// 取出第一队之后,如果后面还有数字的重复就要开始去重// 比如 -1 -1 -1 0 1 1 1 需要保证left和right的值不能相等while (right left nums[right] nums[right - 1]) right--;while (right left nums[left] nums[left 1]) left;// 找到答案之后双指针收缩right--;left;}}}return res;}};通过
