devbox
煮酒与君饮
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

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

作者：煮酒与君饮 | 2024-06-20 10:34:08

赞

踩

两数之和

一、两数之和

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 函数会把下标打乱。

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

二、三数之和

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]，剩余步骤类似两数之和。不过此处需要注意去重，步骤较为复杂，实际解答时更倾向于双指针法。

  1. class Solution {
  2. public:
  3.     vector<vector<int>> threeSum(vector<int>& nums) 
  4.     {
  5.         int n=nums.size();
  6.         if (n<3)   return {};          // 特判
  7.         vector<vector<int> >res;            // 保存结果
  8.         sort(nums.begin(), nums.end());// 排序
  9.         for(int i=0;i<n;i++){
  10.             unordered_set<int> record; //注意在循环内定义
  11.             if(nums[i]>0) return res;  //有序数组，取到大于0时，后面不会再有满足的数
  12.             if(i>0 && nums[i]==nums[i-1]) continue; //对a去重
  13.             for(int j=i+1;j<n;j++){
  14.                 if(j>i+2 && nums[j]==nums[j-1] && nums[j-1]==nums[j-2]) continue;//对b去重
  15.                 int target=-nums[i]-nums[j];
  16.                 if(record.find(target)!=record.end()){ //找到c
  17.                     res.push_back({nums[i],nums[j],target});
  18.                     record.erase(target); //对c去重
  19.                 }
  20.                 else{
  21.                     record.insert(nums[j]);
  22.                 }
  23.             }
  24.         }
  25.         return res;
  26.     }
  27. };

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

  1. class Solution {
  2. public:
  3.     vector<vector<int>> threeSum(vector<int>& nums) 
  4.     {
  5.         int size = nums.size();
  6.         if (size<3)   return {};          // 特判
  7.         vector<vector<int> >res;            // 保存结果
  8.         sort(nums.begin(), nums.end());// 排序
  9.         for (int i=0;i<size;i++)      // 固定第一个数，转化为求两数之和
  10.         {
  11.             if (nums[i]>0)    return res; // 有序数组，取到大于0时，后面不会再有满足的数
  12.             if (i>0 && nums[i]==nums[i-1])  continue;// 去重：如果此数已经选取过，跳过
  13.             // 双指针在nums[i]后面的区间中寻找和为0-nums[i]的另外两个数
  14.             int left=i+1;
  15.             int right=size-1;
  16.             while(left<right){
  17.                 if(nums[left]+nums[right]<-nums[i]){ //和太小，left指针右移
  18.                     left++;
  19.                 }
  20.                 else if(nums[left]+nums[right]>-nums[i]){ //和太大，right指针左移
  21.                     right--;
  22.                 }
  23.                 else{ //找到和为0的三个数
  24.                     res.push_back({nums[i],nums[left],nums[right]});
  25.                     left++;
  26.                     right--;
  27.                     while(left<right && nums[left]==nums[left-1]){ //去重
  28.                         left++;
  29.                     }
  30.                     while(left<right && nums[right]==nums[right+1]){ //去重
  31.                         right--;
  32.                     }
  33.                 }
  34.                 
  35.             }
  36.         }
  37.         return res;
  38.     }
  39. };

三、四数之和

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循环。

  1. class Solution {
  2. public:
  3.     vector<vector<int>> fourSum(vector<int>& nums, int target) {
  4.         vector<vector<int>> res;
  5.         int n=nums.size();
  6.         sort(nums.begin(),nums.end());
  7.         if(n<4) return {};
  8.         for(int i=0;i<n;i++){
  9.             if(i>0 && nums[i]==nums[i-1]) continue;
  10.             for(int j=i+1;j<n;j++){
  11.                 if(j>i+1 && nums[j]==nums[j-1]) continue;
  12.                 int left=j+1;
  13.                 int right=n-1;
  14.                 while(left<right){
  15.                     if(nums[left]+nums[right]<target-nums[i]-nums[j]){
  16.                         left++;
  17.                     }
  18.                     else if(nums[left]+nums[right]>target-nums[i]-nums[j]){
  19.                         right--;
  20.                     }
  21.                     else{
  22.                         res.push_back({nums[i],nums[j],nums[left],nums[right]});
  23.                         left++;
  24.                         right--;
  25.                         while(left<right && nums[left]==nums[left-1]){
  26.                             left++;
  27.                         }
  28.                         while(left<right && nums[right]==nums[right+1]){
  29.                             right--;
  30.                         }
  31.                     }
  32.                 }
  33.             }
  34.         }
  35.         return res;
  36.     }
  37. };

四、四数相加

454. 四数相加 II

        给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：0 <= i, j, k, l < n，nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
        示例 1：输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]    输出：2
        解释：两个元组如下：
        1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
        2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

        解题思路：

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

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

  1. class Solution {
  2. public:
  3.     int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
  4.         int n=nums1.size();
  5.         int target;
  6.         int cnt=0;
  7.         unordered_map<int,int> nums_record;
  8.         for(int i=0;i<n;i++){
  9.             for(int j=0;j<n;j++){
  10.                 target=nums1[i]+nums2[j];
  11.                 nums_record[target]++;
  12.             }
  13.         }
  14.         for(int i=0;i<n;i++){
  15.             for(int j=0;j<n;j++){
  16.                 target=-nums3[i]-nums4[j];
  17.                 if(nums_record.find(target)!=nums_record.end()){
  18.                     cnt+=nums_record[target];
  19.                 }
  20.             }
  21.         }
  22.         
  23.         return cnt;
  24.     }
  25. };

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/煮酒与君饮/article/detail/739525
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号