附近做app的公司,成都企业网站seo技术,厦门室内装修公司,坪山商城网站建设哪家便宜15. 三数之和
给你一个整数数组 nums #xff0c;判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k #xff0c;同时还满足 nums[i] nums[j] nums[k] 0 。请
你返回所有和为 0 且不重复的三元组。
**注意#xff1a;**答案中不可以包含重复…15. 三数之和
给你一个整数数组 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 。思路 容器可能包含多个键相同的键-值对因此需要找到与指定键对应的所有值。为此可使用 multimap::count( )确定有多少个值与指定的键对应再对迭代器递增 以访问这些相邻的值 map 和 multimap 之间的区别在于后者能够存储重复的键而前者只能存储唯一的键。只针对键与值无关 本题使用哈希法过于复杂所以使用双指针法。 首先将数组排序然后有一层for循环i从下标0的地方开始同时定一个下标left 定义在i1的位置上定义下标right 在数组结尾的位置上。依然还是在数组中找到 abc 使得a b c 0我们这里相当于 a nums[i]b nums[left]c nums[right]。如何移动left 和right呢 如果nums[i] nums[left] nums[right] 0 就说明 此时三数之和大了因为数组是排序后了所以right下标就应该向左移动这样才能让三数之和小一些。如果 nums[i] nums[left] nums[right] 0 说明 此时 三数之和小了left 就向右移动才能让三数之和大一些直到left与right相遇为止。
代码
class Solution {
public:vectorvectorint threeSum(vectorint nums) {sort(nums.begin(), nums.end());int left;int right;int count nums.size() - 1;vectorvectorint result;// result.reserve(count255? 256:0);result.reserve(1024);// 预留出空间减少拷贝int i 0;while (i count nums[i] 0) {if (i 0 nums[i] nums[i - 1]) {i;continue;//如果当前元素和上一个元素相同那么就结束这次循环}left i 1;right nums.size() - 1;// left不能超过rightwhile (left right) {if (nums[i] nums[left] nums[right] 0) {right--;// 如果sum0,那么right左移减少sum} else if (nums[i] nums[left] nums[right] 0) {left;// 如果sum0,那么left右移增加sum} else {vectorint temp{nums[i], nums[left], nums[right]};result.push_back(temp);// 如果sum0则当left时sum0那么right--反之也成立left;right--;while (nums[left] nums[left - 1] left right) {left;// 防止出现[-2,0,0,2,2]的情况}while (nums[right] nums[right 1] left right) {right--;}}}i;}return result;}
};
