FilesExpand file tree

master

/

3sum.js

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

44 lines (41 loc) · 1.12 KB

master

/

3sum.js

Copy path

Top

File metadata and controls

• Code
• Blame

44 lines (41 loc) · 1.12 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

35

36

37

38

39

40

41

42

43

44

/**

* @param {number[]} nums

* @return {number[][]}]

*/

var threeSum = function (nums) {

nums.sort(function (a, b) {

// ascending order

return a - b;

});

var ret = [];

var len = nums.length;

// the last pair will be nums[len-3], nums[len-2], nums[len-1]

for (var i = 0; i < len - 2; i++) {

if (i > 0 && nums[i - 1] === nums[i]) {

continue;

}

threeSumBuilder(nums, i, 0 - nums[i], ret);

}

return ret;

};

function threeSumBuilder(nums, i, target, ret) {

var left = i + 1, right = nums.length - 1;

while (left < right) {

if (nums[left] + nums[right] === target) {

var item = [nums[i], nums[left], nums[right]];

ret.push(item);

left++;

while (left < nums.length && nums[left] === nums[left - 1]) {

left++;

}

right--;

while (right >= 0 && nums[right] === nums[right + 1]) {

right--;

}

} else if (nums[left] + nums[right] > target) {

right--;

} else {

left++;

}

}

}