综合文章

# 题目描述

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

注意：答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

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

# 解题思路

由于题目说明了不能有重复的数组, 但是每一个数组中是可以有相同的数字的.

  1. 考虑输入的数组长度小于3的情况;
  2. 先将数组从小到大排序;
  3. 利用for循环以nums[i]为基点数进行遍历;
  4. 在遍历时定义两个起点, 最左侧left (i + 1)和最右侧right (nums.length - 1);
  5. 每次计算nums[i] + nums[left] + nums[right]的值sum;
  6. 若sum大于0则right向左移, 即right--;
  7. 若sum小于0则left向右移, 即left++;
  8. 若sum等于0, 则证明找到了一组数, 依次移动两个起点, 但是每次移动的时候要考虑是否和上一项相等.

# coding

/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function(nums) {
   if (!nums || nums.length < 3) return []
   nums = nums.sort((a, b) => a - b);
   let sum = 0; // 三个数的和
       result = [];
   for (let i = 0; i < nums.length; i++) {
       if (i && nums[i] === nums[i - 1]) continue; // 若当前这一项和上一项相等则跳过
       let left = i + 1;
       let right = nums.length - 1;
       while (left < right) {
           sum = nums[i] + nums[left] + nums[right];
           if (sum > 0) {
               right--;
           } else if (sum < 0) {
               left++;
           } else {
               result.push([nums[i], nums[left++], nums[right--]]);
               while (nums[left] === nums[left - 1]) { // 一直找到不相同的那个坐标
                   left++;
               }
               while (nums[right] === nums[right + 1]) {
                   right--;
               }
           }
       }
   }
   return result;
};

执行用时 :176 ms, 内存消耗 :46 MB

阅读全文

← 两数之和 →