Skip to content

015. 3Sum

难度: Medium

刷题内容

原题连接

  • https://leetcode.com/problems/3sum

内容描述

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)***

代码:

/**
 * @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;
};


回到顶部