15. Sum of three

Link: https://leetcode-cn.com/problems/3sum/

See the link for the title description.

Solution 1: triple cycle + HasH de duplication

I couldn't think of any good idea, so I started it in a stupid way, compared it with three cycles, saved the existing results with a HasH, and made the first two numbers of the results as key s, which was violent enough

var threeSum = function (nums) {
  const len = nums.length;
  if (len < 3) {
    return [];
  }
  const hash = {},
    result = [];

  for (let i = 0; i < len; i++) {
    for (let j = i + 1; j < len; j++) {
      for (let k = j + 1; k < len; k++) {
        if (nums[i] + nums[k] + nums[j] === 0) {
          const temp = [nums[i], nums[k], nums[j]].sort((prev, next) => prev - next),
            key = `${temp[0]}-${temp[1]}`;

          if (!hash[key]) {
            result.push(temp);
            hash[key] = true;
          }
        }
      }
    }
  }

  return result;
};

• Time complexity: ${O(N^3)}$
• Space complexity: ${O(N)}$
• Execution time: unexpected timeout

Solution 2: triple cycle + sorting

The following is the official problem solution for optimization. First, optimize the HasH de duplication problem. You can sort the array from small to large, so that when we find a qualified array [- 1, 0, 1], [0, - 1, 1], this kind of repeated array will not be found again

In addition, for each iteration, if the elements of the two adjacent enumerations are the same, the results are also repeated. For example, [0, 1, 2, 2]. After finding [0, 1, 2], if the third iteration continues, it will still find [0, 1, 2]. Therefore, it is necessary to de duplicate the elements with the same values of the two adjacent enumerations

var threeSum = function (nums) {
  const len = nums.length,
    sorted = nums.sort((a, b) => a - b);
  if (len < 3) {
    return [];
  }
  const result = [];

  for (let i = 0; i < len; i++) {
    const first = sorted[i];
    if (i > 0 && first === sorted[i - 1]) {
      continue;
    }
    for (let j = i + 1; j < len; j++) {
      const second = sorted[j];
      if (j > i + 1 && second === sorted[j - 1]) {
        continue;
      }

      for (let k = j + 1; k < len; k++) {
        const third = sorted[k];
        if (k > j + 1 && third === sorted[k - 1]) {
          continue;
        }
        if (first + second + third === 0) {
          result.push([sorted[i], nums[k], nums[j]]);
        }
      }
    }
  }

  return result;
};

• Time complexity: ${O(N^3)}$
• Space complexity: ${O(1)}$
• Execution time: still timeout

Solution 3: sorting + double pointer

Triple loops are still needed above. The optimization method is to use double pointers. Because the array has been sorted, after a cardinality x is fixed in a loop, the second loop can find the second number and the third number at the same time

Declare two pointers, start and end. Start points to the starting point of the double cycle, and end points to the end point. Num [start] must be less than num [End]. Our goal is to find the case where num [start] and num [End] are equal to - x. discuss the case by case:

• Num [start] + num [End] < - X. at this time, move start one bit to the right to make num [start] larger and continue to search
• Num [start] + num [End] > - X. at this time, move end one bit to the left to make num [End] smaller and continue to search
• Num [start] + num [End] = = = - X. This is the case we need to find. Save it and shrink start and end inward at the same time. Pay attention to de duplication. De duplication is only necessary in this case. If num [start] and num [start - 1] are equal, the result must be repeated, so we need to continue to increase start, and end is the same

var threeSum = function (nums) {
  const len = nums.length,
    sorted = nums.sort((a, b) => a - b);
  if (len < 3) {
    return [];
  }
  const result = [];

  for (let i = 0; i < len; i++) {
    const first = sorted[i];
    if (first > 0) {
      return result;
    }

    if (i > 0 && first === sorted[i - 1]) {
      continue;
    }

    let start = i + 1,
      end = len - 1;

    while (start < end) {
      const second = sorted[start],
        third = sorted[end],
        target = -first;

      const temp = second + third;
      if (temp > target) {
        end -= 1;
      } else if (temp < target) {
        start += 1;
      } else {
        result.push([first, second, third]);
        end -= 1;
        start += 1;

        // start repeat element
        while (start < end && sorted[start] === sorted[start - 1]) {
          start += 1;
        }

        // end duplicate element
        while (start < end && sorted[end] === sorted[end + 1]) {
          end -= 1;
        }
      }
    }
  }

  return result;
};

• Time complexity: ${O(N^2)}$
• Space complexity: ${O(1)}$
• Execution time: 124ms, beat 100% of users in all JavaScript submissions, memory consumption: 47.6MB, beat 91% of users in all JavaScript submissions