0015._Three_Sum

发表于 分类于 ， ，

015. 3Sum

难度: Medium

刷题内容

原题连接

内容描述

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

 The solution set must not contain duplicate triplets.

Example:

 Given array nums = [-1, 0, 1, 2, -1, -4],
 
 A solution set is:
 [
   [-1, 0, 1],
   [-1, -1, 2]
 ]

解题方案

思路
**- 时间复杂度: O(N²)**- 空间复杂度: O(N)**

代码：

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
31
32
33
34
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
let threeSum = function(nums, n = 0) {
    let result = [];
    let len = nums.length;
    if(!len) return result;
    // 对数组进行排序
    nums.sort((a,b)=>a-b);
    for(let k = 0; k<len; k++){
        //重复的元素则结果也一样，所以跳过该循环
        if(k>0 && nums[k-1] === nums[k]){
            continue;
        }
        let target = n - nums[k];
        let i = k + 1;
        let j = len -1;
        while(i<j){
            if(nums[i] + nums[j] === target){
                result.push([nums[k],nums[i],nums[j]]);
                while (i<j && nums[i] === nums[i+1]) i++;
                while (i<j && nums[j] === nums[j-1]) j--;
                i++;
                j--;
            }else if(nums[i] + nums[j] > target){
                j--;
            }else{
                i++
            }
        }
    }
    return result;
};