preface

About the LeetCode array type problem related solutions, it can be seen that LeetCode array type problem before doing must see, classification solution summarized the problem, can be used to improve a single. If you think it is helpful, remember to give more likes and attention, thank you!

Topic describes

Given an array of n integers, nums, determine if there are three elements a, b, and c in NUMs such that a + b + c = 0? Find all triples that sum 0 and are not repeated.

Note: Answers may not contain duplicate triples.

Example 1: input: nums = [1, 2, 1, 4] output: [[1, 1, 2], [1, 1]]

Example 2: Input: nums = [] Output: []

Example 3: Input: nums = [0] Output: []

Link: leetcode-cn.com/problems/3s…

Answer key

  1. Violent solution, starting from position 0, iterates through the elements at each position successively. When the sum of three elements is 0, it is added to a set to prevent repetition. The time complexity of this method is O(n³).
  2. If we fix element A one at a time, then the problem is converted to the problem of Leetcode 1 2sum, finding the combination of the two elements that sum to -a of the remaining elements. In this case, we’re using a double pointer to find these two elements, and since they don’t want to duplicate triples, we can sort the array first, filter out the same elements, and then we can use the sorted array to subtract. The time complexity of this method is O(n²).
/ * * *@param {number[]} nums
 * @return {number[][]}* /
var threeSum = function (nums) {
  if (nums.length < 3) {
    return [];
  }
  let ans = [];
  nums = nums.sort((a, b) = > a - b);
  for (let index = 0; index < nums.length - 2; index++) {
    if (nums[index] > 0) break; // If the current element is already greater than 0, no further traversal is required
    if (index > 0 && nums[index - 1] === nums[index]) {
      continue;  // Exclude the same elements to prevent repeated answers
    }
    const element = nums[index];
    let l = index + 1;
    let r = nums.length - 1; / / double pointer
    while (l < r) {
      if (element + nums[l] + nums[r] === 0) {
        ans.push([element, nums[l++], nums[r--]]);
        while (l < r && nums[l] === nums[l - 1]) { // Exclude the same elements to prevent repeated answers
          l++;
        }
        while (l < r && nums[r] === nums[r + 1]) { // Exclude the same elements to prevent repeated answersr--; }}else if (nums[l] + nums[r] + element > 0) {
        r--;
      } else{ l++; }}}return ans;
};
Copy the code