上海网站建设觉策动力,大公司的网站都找谁设计,深圳高端企业官方网站建设,网站制作视频教程免费前言
欢迎来到小K的Leetcode|代码随想录|专题化专栏#xff0c;今天将为大家带来哈希法~三数之和 | 四数之和的分享✨ 目录 前言15. 三数之和18. 四数之和总结 15. 三数之和
✨题目链接点这里 给你一个整数数组 nums #xff0c;判断是否存在三元组 [nums[i], nums[j], num…前言
欢迎来到小K的Leetcode|代码随想录|专题化专栏今天将为大家带来哈希法~三数之和 | 四数之和的分享✨ 目录 前言15. 三数之和18. 四数之和总结 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 。
提示 3 nums.length 3000 -105 nums[i] 105
「方法一」哈希法直接两层for循环确定第一个和第二个数然后在哈希表中查找最后一个数思路没有问题但是实现起来很困难就是去重的问题和时间复杂度的问题去重主要是第二个数的去重【因为数组已经排序如果连续的三个数字相同那么它们组成的三元组只能是一种情况不需要重复计算】第二个就是时间复杂度的问题这个真不好解决只能注意去重的细节因为本身就有两个for循环在加上erase和insert操作~我这里是险过
class Solution {
public:vectorvectorint threeSum(vectorint nums) {vectorvectorint result;sort(nums.begin() , nums.end());for (int i 0; inums.size(); i) {if (nums[i] 0) break;if (i 0 nums[i] nums[i-1]) continue;unordered_setint set;for (int j i 1; j nums.size(); j) {if (j i 2 nums[j] nums[j-1] nums[j-1] nums[j-2]) continue;int c - (nums[i] nums[j]);if (set.find(c) ! set.end()) {result.push_back({nums[i] , nums[j] , c});set.erase(c);}else set.insert(nums[j]);}}return result;}
};「方法二」双指针法
拿这个nums数组来举例首先将数组排序然后有一层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相遇为止。
Tips这里说答案中不可以包含重复的三元组并不是说三元组中不能有重复元素但是重复元素不能是同一位置所以这里去重使用的是nums[i] nums[i-1]而不是nums[i] nums[i1]
class Solution {
public:vectorvectorint threeSum(vectorint nums) {vectorvectorint result;sort(nums.begin() , nums.end());for (int i 0; i nums.size(); i) {if (nums[i] 0) return result;if (i 0 nums[i] nums[i-1]) continue;int left i 1;int right nums.size() - 1;while (left right) {if (nums[i] nums[left] nums[right] 0) right--;else if(nums[i] nums[left] nums[right] 0) left;else {result.push_back(vectorint{nums[i] , nums[left] , nums[right]});while (left right nums[right] nums[right-1]) right--;while (left right nums[left] nums[left1]) left;left , right--;}}}return result;}
};18. 四数之和
✨题目链接点这里 给你一个由 n 个整数组成的数组 nums 和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组[nums[a], nums[b], nums[c], nums[d]]若两个四元组元素一一对应则认为两个四元组重复0 a, b, c, d na、b、c 和 d 互不相同nums[a] nums[b] nums[c] nums[d] target你可以按 任意顺序 返回答案 。
示例 1 输入nums [1,0,-1,0,-2,2], target 0 输出[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2 输入nums [2,2,2,2,2], target 8 输出[[2,2,2,2]]
提示 1 nums.length 200 -109 nums[i] 109 -109 target 109
使用双指针和上一题思路一样只是多加了一层for循环
class Solution {
public:vectorvectorint fourSum(vectorint nums, int target) {vectorvectorint result;sort(nums.begin() , nums.end());for (int k 0; k nums.size(); k) {if (nums[k] target nums[k] 0) break;if (k 0 nums[k] nums[k-1]) continue;for (int i k 1; i nums.size(); i) {if (nums[k] nums[i] target nums[k] nums[i] 0 ) break;if (i k 1 nums[i] nums[i-1]) continue;int left i 1;int right nums.size() - 1;while (left right) {if (nums[k] nums[i] target - nums[left] - nums[right]) right--;else if (nums[k] nums[i] target - nums[left] - nums[right]) left;else {result.push_back({nums[k] , nums[i] , nums[left] , nums[right]});while (left right nums[right] nums[right-1]) right--;while (left right nums[left] nums[left1]) left;left , right--; }}}}return result;}
};总结
要恰当使用哈希法并根据实际情况选择合适的结构数组setmap
