两数之和、三数之和、四数之和还不会写？看完此篇轻松掌握

大家好，欢迎来到IT知识分享网。

一、两数之和

1. 两数之和

        给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target  的那两个整数，并返回它们的数组下标。

        示例 1：输入：nums = [2,7,11,15], target = 9        输出：[0,1]        解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

        解题思路：

        此题使用哈希法，对数组进行一次遍历，如果哈希表中能查询到 target-nums[i]，代表找到了和为target的两数，如果不能查询到 target-nums[i]，则向哈希表中插入nums[i]，确保后面的查找。        

        注意此题不可用双指针解法，因为 sort 函数会把下标打乱。

class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int,int> hashtable; for(int i=0;i<nums.size();i++){ auto it=hashtable.find(target-nums[i]); if(it!=hashtable.end()){ return {it->second,i}; } hashtable[nums[i]]=i;//注意nums[i]是键值，i是键值对应的元素值 //hashtable.insert(pair<int,int>(nums[i],i)); 插入键值对的另外一种写法 } return {}; } };

二、三数之和

15. 三数之和

        给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

        示例 1：输入：nums = [-1,0,1,2,-1,-4]        输出：[[-1,-1,2],[-1,0,1]]

        解题思路：

        此题有两种解法：哈希解法和双指针法。

        哈希解法：通过两层 for 循环确定 a 和 b, 得出 target=-nums[i]-nums[j]，剩余步骤类似两数之和。不过此处需要注意去重，步骤较为复杂，实际解答时更倾向于双指针法。

class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { int n=nums.size(); if (n<3) return {}; // 特判 vector<vector<int> >res; // 保存结果 sort(nums.begin(), nums.end());// 排序 for(int i=0;i<n;i++){ unordered_set<int> record; //注意在循环内定义 if(nums[i]>0) return res; //有序数组，取到大于0时，后面不会再有满足的数 if(i>0 && nums[i]==nums[i-1]) continue; //对a去重 for(int j=i+1;j<n;j++){ if(j>i+2 && nums[j]==nums[j-1] && nums[j-1]==nums[j-2]) continue;//对b去重 int target=-nums[i]-nums[j]; if(record.find(target)!=record.end()){ //找到c res.push_back({nums[i],nums[j],target}); record.erase(target); //对c去重 } else{ record.insert(nums[j]); } } } return res; } };

         双指针法：运用for循环，遍历数组固定第一个数a ，将问题转化为求两数之和。双指针在 nums[i] 后面的区间中寻找和为 0-nums[i] 的另外两个数，left 指针指向 i+1，right 指针指向 size-1, 不断缩小区间 [left,right]，找到 a 确定时满足的所有组合。

class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { int size = nums.size(); if (size<3) return {}; // 特判 vector<vector<int> >res; // 保存结果 sort(nums.begin(), nums.end());// 排序 for (int i=0;i<size;i++) // 固定第一个数，转化为求两数之和 { if (nums[i]>0) return res; // 有序数组，取到大于0时，后面不会再有满足的数 if (i>0 && nums[i]==nums[i-1]) continue;// 去重：如果此数已经选取过，跳过 // 双指针在nums[i]后面的区间中寻找和为0-nums[i]的另外两个数 int left=i+1; int right=size-1; while(left<right){ if(nums[left]+nums[right]<-nums[i]){ //和太小，left指针右移 left++; } else if(nums[left]+nums[right]>-nums[i]){ //和太大，right指针左移 right--; } else{ //找到和为0的三个数 res.push_back({nums[i],nums[left],nums[right]}); left++; right--; while(left<right && nums[left]==nums[left-1]){ //去重 left++; } while(left<right && nums[right]==nums[right+1]){ //去重 right--; } } } } return res; } };

三、四数之和

18. 四数之和

        给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：0 <= a, b, c, d < n， a、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]]

        解题思路：

        与三数之和类似，只是多一层for循环。

class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { vector<vector<int>> res; int n=nums.size(); sort(nums.begin(),nums.end()); if(n<4) return {}; for(int i=0;i<n;i++){ if(i>0 && nums[i]==nums[i-1]) continue; for(int j=i+1;j<n;j++){ if(j>i+1 && nums[j]==nums[j-1]) continue; int left=j+1; int right=n-1; while(left<right){ if(nums[left]+nums[right]<target-nums[i]-nums[j]){ left++; } else if(nums[left]+nums[right]>target-nums[i]-nums[j]){ right--; } else{ res.push_back({nums[i],nums[j],nums[left],nums[right]}); left++; right--; while(left<right && nums[left]==nums[left-1]){ left++; } while(left<right && nums[right]==nums[right+1]){ right--; } } } } } return res; } };

四、四数相加

454. 四数相加 II

        解题思路：

        此题与上述题目不太一样，是分别从四个数组里面选一个数，但也是使用哈希法，首先，可以先在 nums1 和 nums2 里面选出第一个数和第二个数，用两个 for 循环进行枚举遍历， 并将这两个数的和插入哈希表。

        再在 nums3 和 nums4 里面枚举遍历选出第三个数和第四个数，查询哈希表里是否有键值等于 target =-nums3[i]-nums4[j]，若找到有，则总次数加上此 target 在哈希表中记录的次数，若没找到，则继续进行下一次枚举。

class Solution { public: int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) { int n=nums1.size(); int target; int cnt=0; unordered_map<int,int> nums_record; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ target=nums1[i]+nums2[j]; nums_record[target]++; } } for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ target=-nums3[i]-nums4[j]; if(nums_record.find(target)!=nums_record.end()){ cnt+=nums_record[target]; } } } return cnt; } };