luzhipeng edf7916 May 3, 2019
0 contributors

Users who have contributed to this file

128 lines (109 sloc) 3.31 KB

题目地址

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

题目描述

``````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]
]

``````

• 排序之后，用双指针
• 分治

代码

```/*
* @lc app=leetcode id=15 lang=javascript
*
* [15] 3Sum
*
* https://leetcode.com/problems/3sum/description/
*
* algorithms
* Medium (23.51%)
* Total Accepted:    531.5K
* Total Submissions: 2.2M
* Testcase Example:  '[-1,0,1,2,-1,-4]'
*
* 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]
* ]
*
*
*/
/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function(nums) {
if (nums.length < 3) return [];
const list = [];
nums.sort((a, b) => a - b);
for (let i = 0; i < nums.length; i++) {
// skip duplicated result without set
if (i > 0 && nums[i] === nums[i - 1]) continue;
let left = i;
let right = nums.length - 1;

// for each index i
// we want to find the triplet [i, left, right] which sum to 0
while (left < right) {
// skip i === left or i === right, in that case, the index i will be used twice
if (left === i) {
left++;
} else if (right === i) {
right--;
} else if (nums[left] + nums[right] + nums[i] === 0) {
list.push([nums[left], nums[right], nums[i]]);
// skip duplicated result without set
while(nums[left] === nums[left + 1]) {
left++;
}
left++;
// skip duplicated result without set
while(nums[right] === nums[right - 1]) {
right--;
}
right--;
continue;
} else if (nums[left] + nums[right] + nums[i] > 0) {
right--;
} else {
left++;
}
}
}
return list;
};```
You can’t perform that action at this time.