leetcode_js/18. 4Sum.js at master · jawang94/leetcode_js · GitHub

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function(nums, target) {
  var results = [];
  nums.sort(function(a, b) {
    return a - b;
  });
  for (var i = 0; i < nums.length - 3; i++) {
    while (i > 0 && i < nums.length - 3 && nums[i] === nums[i - 1]) {
      i++;
    }
    for (var j = i + 1; j < nums.length - 2; j++) {
      while (j > i + 1 && j < nums.length - 2 && nums[j] === nums[j - 1]) {
        j++;
      }
      var low = j + 1;
      var high = nums.length - 1;
      var newTarget = target - (nums[i] + nums[j]);
      while (low < high) {
        partialSum = nums[low] + nums[high];
        if (partialSum === newTarget) {
          results.push([nums[i], nums[j], nums[low], nums[high]]);
          high--;
          low++;
          while (low < high && nums[low] === nums[low - 1]) {
            low++;
          }
          while (low < high && nums[high] === nums[high + 1]) {
            high--;
          }
        } else if (partialSum > newTarget) {
          high--;
        } else {
          low++;
        }
      }
    }
  }
  return results;
};

// Solution 2 (more stable than solution 1). Consistently 92ms, as low as 88ms faster than 97.45%
var fourSum = function(nums, target) {
  var ret = [];

  if (nums.length == 0) return ret;

  nums.sort(function(a, b) {
    return a - b;
  });

  for (var i = 0; i < nums.length; i++) {
    var target2 = target - nums[i];

    for (var j = i + 1; j < nums.length; j++) {
      var target3 = target2 - nums[j];

      var front = j + 1;
      var back = nums.length - 1;

      while (front < back) {
        var sum = nums[front] + nums[back];

        if (sum < target3) front++;
        else if (sum > target3) back--;
        else {
          var temp = new Array(4);
          temp[0] = nums[i];
          temp[1] = nums[j];
          temp[2] = nums[front];
          temp[3] = nums[back];
          ret.push(temp);

          while (front < back && nums[front] === temp[2]) front++;

          while (front < back && nums[back] === temp[3]) back--;
        }
      }

      while (j + 1 < nums.length && nums[j + 1] === nums[j]) ++j;
    }

    while (i + 1 < nums.length && nums[i + 1] === nums[i]) ++i;
  }

  return ret;
};

// Refactored final solution
const fourSum = (nums, target) => {
  let result = [];

  if (nums.length == 0) return result;

  nums.sort(function(a, b) {
    return a - b;
  });

  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      let newTarget = target - (nums[i] + nums[j]);

      let front = j + 1;
      let back = nums.length - 1;

      while (front < back) {
        let sum = nums[front] + nums[back];

        if (sum < newTarget) ++front;
        else if (sum > newTarget) --back;
        else {
          let frontMarker = nums[front];
          let backMarker = nums[back];

          result.push([nums[i], nums[j], frontMarker, backMarker]);
          front++;
          back--;

          while (front < back && nums[front] === frontMarker) ++front;
          while (front < back && nums[back] === backMarker) --back;
        }
      }

      while (j + 1 < nums.length && nums[j + 1] === nums[j]) ++j;
    }

    while (i + 1 < nums.length && nums[i + 1] === nums[i]) ++i;
  }

  return result;
};