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

大家好今天给大家分享下一道 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-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)
*/

总结

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

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

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

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