Title description:

LeetCode address

Tag: Array
Difficulty: Easy
Description:

Given an integer array nums and an integer target value target, find the two integers in the array and the target value target and return their array subscripts.

You can assume that there is only one answer for each type of input. However, the same element in the array cannot be repeated in the answer.

You can return the answers in any order.

Example 1:
Input: nums = [2,7,11,15], target = 9 output: [0,1]Copy the code
Example 2:
Input: nums = [3,2,4], target = 6Copy the code
Example 3:
Input: nums = [3,3], target = 6Copy the code
Tip:
  • 2 <= nums.length <= 104
  • 109 <= nums[i] <= 109
  • 109 <= target <= 109
  • There can only be one valid answer

Answer key

Subject to understand

Note: the title calls for “non-repeating triples”, and we need to deal with the case of duplicate elements.

Their thinking

  1. Core idea: sort + collision double pointer

code

/ * * *@param {number[]} nums
 * @return {number[][]}* /
var threeSum = function(nums) {
    let result = [];
    nums.sort((a, b) = > a - b);
    const len = nums.length;

    for(let i = 0; i < len - 2; i++) {
        let l = i + 1, r = len - 1;
        if (i > 0 && nums[i] === nums[i - 1]) {
            continue;
        }
        while(l < r) {
            if (nums[i] + nums[l] + nums[r] < 0) {
                l++;
                while(l < r && nums[l] === nums[l - 1]) { l++; }}else if (nums[i] + nums[l] + nums[r] > 0) {
                r--;
                while(l < r && nums[r] === nums[r + 1]) { r--; }}else {
                result.push([nums[i], nums[l], nums[r]]);
                l++;
                r--;
                while(l < r && nums[l] === nums[l - 1]) {
                    l++;
                }
                while(l < r && nums[r] === nums[r + 1]) { r--; }}}}return result;
};
Copy the code

Algorithm analysis

  1. Time complexity: O(n^2)
  2. Space complexity: O(logn)

conclusion

  1. Array sort method
  2. Bidirectional pointer, collision pointer algorithm
    • Iterate through the array from both ends to the middle. One pointer starts at the beginning and the other at the end;
    • The termination condition is that two Pointers meet;
    • Often used to sort an array.