​LeetCode刷题实战18: 四数之和

程序IT圈

共 761字,需浏览 2分钟

 ·

2020-08-24 02:55

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !


今天和大家聊的问题叫做四数之和 ,我们先来看题面:

https://leetcode-cn.com/problems/4sum/

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.


题意


给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + c + d 的值与 target 相等?找出所有满足条件且不重复的四元组。
注意:答案中不可以包含重复的四元组。

样例


给定数组 nums = [1, 0, -1, 0, -2, 2],和 target = 0

满足要求的四元组集合为:
[
  [-1, 0, 0, 1
],
  [-2, -1, 1, 2],
  [-2, 0, 0, 2]
]



题解


四数之和与前面三数之和的思路几乎是一样的 。在前面的基础上多添加一个遍历的指针 。

使用四个指针(a
保存使得nums[a]+nums[b]+nums[c]+nums[d]==target的解。偏大时d左移,偏小时c右移。c和d相遇时,表示以当前的a和b为最小值的解已经全部求得。b++,进入下一轮循环b循环,当b循环结束后。
a++,进入下一轮a循环。即(a在最外层循环,里面嵌套b循环,再嵌套双指针c,d包夹求解)。


class Solution{
  public:
  vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(),nums.end());
        vector<vector<int> > res;
        if(nums.size()<4)
        return res;
        int a,b,c,d,_size=nums.size();
        for(a=0;a<=_size-4;a++){
          if(a>0&&nums[a]==nums[a-1]) continue; //确保nums[a] 改变了
          for(b=a+1;b<=_size-3;b++){
            if(b>a+1&&nums[b]==nums[b-1])continue; //确保nums[b] 改变了
            c=b+1,d=_size-1;
            while(c              if(nums[a]+nums[b]+nums[c]+nums[d]                  c++;
              else if(nums[a]+nums[b]+nums[c]+nums[d]>target)
                  d--;
              else{
                res.push_back({nums[a],nums[b],nums[c],nums[d]});
                while(c1]==nums[c]) //确保nums[c] 改变了
                    c++;
                while(c-1]==nums[d]) //确保nums[d] 改变了
                    d--;
                c++;
                d--;
          }
        }
      }
    }
    return res;
    }
};

作者:misakasagiri-2
链接:https://leetcode-cn.com/problems/4sum/solution/shuang-zhi-zhen-jie-fa-can-zhao-san-shu-zhi-he-ge-/


今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力。


上期推文:


LeetCode刷题实战1:在数组上遍历出花样

LeetCode刷题实战2:用链表模拟加法

LeetCode刷题实战3:最长不重复子串

LeetCode刷题实战4:两个正序数组的中位数

LeetCode刷题实战5:判断回文子串

LeetCode刷题实战6:Z字形变换

LeetCode刷题实战7:整数反转

LeetCode刷题实战8:字符串转换整数

LeetCode刷题实战9:求解回文数

LeetCode刷题实战10:字符串正则匹配

LeetCode刷题实战11: 盛最多水的容器

LeetCode刷题实战12: 整数转罗马数字

LeetCode刷题实战13: 罗马数字转整数

LeetCode刷题实战14: 最长公共前缀

LeetCode刷题实战15:三数之和

LeetCode刷题实战16: 最接近的三数之和

LeetCode刷题实战17: 电话号码的字母组合


浏览 33
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报