三数之和

发表于 | 阅读次数: |

题目
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件的三元组。
注意：答案中可以包含重复的三元组。

示例

1
2
3
4
5
6
给定数组 nums = [-1, 0, 1, 2, -1, -4]，满足要求的三元组集合为：  
[
  [-1, 0, 1],
  [-1, -1, 2],
  [0, 1, -1]
]

解题思路
通过循环数组，把数组中的值左右比较，得到最终的 target 值。

CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
function threeNumArr(nums) {
  let left, right, target, result = [], numArr = [];

  if (!nums || nums.length < 3) return [];

  for (let i = 0; i < nums.length - 2; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) {
      continue;
    }

    left = i + 1;
    right = nums.length - 1;
    target = nums[i];

    for (let j = left; j < right - 1; j++) {
      for (let k = left + 1; k < right; k++) {
        if (nums[j] + nums[k] === -target) {
          numArr.push(target);
          numArr.push(nums[j]);
          numArr.push(nums[k]);

          result.push(numArr);
          numArr = [];
        }  
      }
    }
  }

  return result;
};

总结
在上面是直接找出数组中能够满足条件的所有数值且重复也没有关系，可以全部输出。但是通过上面的循环操作时间复杂度就比较大了。再或者，不允许存在重复的值的情况时，又该怎么处理？