FilesExpand file tree

master

/

4sum.js

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

47 lines (44 loc) · 1.25 KB

master

/

4sum.js

Copy path

Top

File metadata and controls

• Code
• Blame

47 lines (44 loc) · 1.25 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

45

46

47

/**

* @param {number[]} nums

* @param {number} target

* @return {number[][]}

*/

var fourSum = function (nums, target) {

var ret = [];

nums.sort(function (a, b) {

return a - b;

});

for (var i = 0; i <= nums.length - 4; i++) {

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

continue;

}

for (var j = i + 1; j <= nums.length - 3; j++) {

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

continue;

}

fourSumBuilder(nums, target - nums[i] - nums[j], i, j, ret);

}

}

return ret;

};

function fourSumBuilder(nums, target, prev, start, ret) {

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

while (left < right) {

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

var item = [nums[prev], nums[start], 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) {

left++;

} else {

right--;

}

}

}