最新公告
  • 欢迎您光临起源地模板网,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入钻石VIP
  • LeetCode算法学习之--数组--三数之和

    正文概述 掘金(坚定)   2021-07-24   30

    大家好今天给大家分享下一道 LeetCode 中等难度 的题目 三数之和

    题目

    分析

    解法一:暴力法(通过不了,只提供思路)

    思路
    1.三层遍历数组 判断每一种可能性
    2.添加set 来防止重复
    3.一定要排序,不然会统计到重复的数据
    */
    var threeSum = function (nums) {
      const set = new Set();
      const res = [];
      //  一定要排序 不然组合不好统计 例如 [[-1,0,1],[-1,2,-1],[0,1,-1]]
      nums.sort((a, b) => a - b);
      // 第一层可以是 nums.length - 2, 因为给 j 和k 留2个位置,同理如下
      for (let i = 0; i < nums.length - 2; i++) {
        // 第二层的起点是 j=i+1,因为是题目不能同一个位置上的同一个元素不能选择2次,同理如下
        for (let j = i + 1; j < nums.length - 1; j++) {
          for (let k = j + 1; k < nums.length; k++) {
            const key = nums[i] + "_" + nums[j] + "_" + nums[k];
            if (nums[i] + nums[k] + nums[j] === 0 && !set.has(key)) {
              res.push([nums[i], nums[k], nums[j]]);
              set.add(key);
            }
          }
        }
      }
    
      return res;
    };
    
    /* 复杂度
    时间 O(n^3)
    空间 O(1)
    */
    

    解法二:Set 法

    代码借鉴 leetcode-cn.com/problems/3s…

    1.排序 避免重复,
    2.因为不能有重复的三元组,所以利用Set 来去重
    3.采用遍历的方式, 看下是否能获取 三个元素相加为0 的情况
    4.暴力法不同的地方在于, 不再采用第三层遍历,而是使用Set的方法来判断是否存在 v= -nums[i] - nums[j],
    因为set的查询时间复杂度为O(1) 所以总的复杂度为O(n^2)
    */
    
    var threeSum = function (nums) {
      const res = [];
      // 去重使用
      const uniqueSet = new Set();
      nums.sort((a, b) => a - b);
    
      for (let i = 0; i < nums.length - 1; i++) {
        // 存放 nums[j]的值
        const set = new Set();
        for (let j = i + 1; j < nums.length; j++) {
          // 需要求得的值
          const v = -nums[i] - nums[j];
          // 三元数组的唯一标识,放入set中防止重复取值
          const str = nums[i] + "_" + v + "_" + nums[j];
          if (set.has(v) && !uniqueSet.has(str)) {
            res.push([nums[i], v, nums[j]]);
            uniqueSet.add(str);
          } else {
            set.add(nums[j]);
          }
        }
      }
      return res;
    };
    
    /* 复杂都
    时间 O(n^2)
    空间 O(n)
    */
    

    LeetCode算法学习之--数组--三数之和

    解法二:双指针

    代码借鉴 leetcode-cn.com/problems/3s…

    思路
    1.排序防止重复
    2.遍历一次元素,获取一个三个元素中的一个,nums[i],
    3.再次遍历一次数组,利用双指针 左边放置一个指针j 右边放置一个指针k,往中间内夹
    令 sum = nums[i]+nums[j]+nums[k],因为数组有序
    如果sum>0 则左边k对应的值大了 所以应该
    */
    
    var threeSum = function (nums) {
      const res = [];
      // 老规矩 排序防止重复的情况发生
      nums.sort((a, b) => a - b);
      // 遍历
      for (let i = 0; i < nums.length; i++) {
        // 如果nums[i]都已经大于0了, 那么其他元素相加不可能再等于零 所以直接break
        if (nums[i] > 0) break;
        // 说明有重复, 但是不能判断 nums[i]===nums[i+1]的时候就continue 因为会错过元素例如(-1,-1,2) 这种情况就会被错过
        if (i > 0 && nums[i - 1] === nums[i]) continue;
    
        for (let j = i + 1, k = nums.length - 1; j < k; ) {
          const sum = nums[i] + nums[j] + nums[k];
          // 说明nums[k]大了, 所以需要k--
          if (sum > 0) {
            k--;
            // 说明nums[j]小了, 所以需要j++
          } else if (sum < 0) {
            j++;
          } else {
            // 说明找到了答案了
            res.push([nums[i], nums[j], nums[k]]);
            while (j < k && nums[j] === nums[j + 1]) j++;
            while (j < k && nums[k] === nums[k - 1]) k--;
            j++;
            k--;
          }
        }
      }
    
      return res;
    };
    /* 复杂度
    时间 O(n^2)
    空间 O(1)
    */
    

    LeetCode算法学习之--数组--三数之和

    总结

    这道题 ,考察大家对双指针 和 Set的理解,因为他们可以很好的降低时间复杂度

    大家可以看看我分享的一个专栏(前端搞算法)里面有更多关于算法的题目的分享,希望能够帮到大家,我会尽量保持每天晚上更新,如果喜欢的麻烦帮我点个赞,十分感谢

    文章内容目的在于学习讨论与分享学习算法过程中的心得体会,文中部分素材来源网络,如有侵权,请联系删除,邮箱 182450609@qq.com

    今天很有幸的去支持了下鸿星尔克和蜜雪冰城,不得不说为中国的良心企业点赞,为我的祖国感到骄傲,郑州加油!河南加油!中国加油!


    起源地 » LeetCode算法学习之--数组--三数之和

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用?
    本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。若排除这种情况,可在对应资源底部留言,或 联络我们.。
    找不到素材资源介绍文章里的示例图片?
    对于PPT,KEY,Mockups,APP,网页模版等类型的素材,文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买,且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况,但部分素材会在素材包内有一份字体下载链接清单。
    模板不会安装或需要功能定制以及二次开发?
    请QQ联系我们

    发表评论

    还没有评论,快来抢沙发吧!

    如需帝国cms功能定制以及二次开发请联系我们

    联系作者

    请选择支付方式

    ×
    迅虎支付宝
    迅虎微信
    支付宝当面付
    余额支付
    ×
    微信扫码支付 0 元