“This is the 8th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

In a broad sense, a double pointer is a problem solved by traversing a linear structure with two variables. In a narrow sense,

  • In the case of an array, it is a problem solved by moving two variables across the array.
  • For linked lists, it refers to the problem solved by two variables moving in the same direction on the linked list, also known as the “fast or slow pointer” problem.

Double pointer algorithm is usually not difficult, double pointer algorithm is based on the optimization of the violent solution, it is a good entry problem to learn the algorithm.

This paper presents two similar, progressive “two-pointer” algorithm problems.

Blunt is done roar ~~

“The sum of the nearest three”

You are given an array of integers of length n nums and a target value target. Select three integers from nums whose sum is closest to target.

Returns the sum of these three numbers.

Assume that exactly one solution exists for each set of inputs.

Example 1: Input: nums = [-1,2,1,-4], target = 1 Output: 2 Explanation: The closest sum to target is 2 (-1 + 2 + 1 = 2). Example 2: Input: nums = [0,0,0] target = 1 Output: 0Copy the code

Two-pointer solution:

The array is sorted in ascending order, initializing a minimum sum; Iterate over the number group, define a double pointer, if the current and are closer, update the minimum; Moves the pointer according to the relationship between the sum of the current three digits and target; If the sum of three numbers equals target during traversal, return the current sum.

Const threesumps = (nums, target) => { // initialize a minimum value let min = Infinity; const len = nums.length; for (let i = 0; i < len; I ++) {let [left, right] = [I + 1, len-1]; While (left < right) {const sum = nums[I] + nums[left] + nums[right]; // If (math.abs (sum-target) < math.abs (min-target)) {min = sum; If (sum < target) {left++; } else if (sum > target) { right--; } else {// sum = target; }}} // return the nearest and return min; };Copy the code

“Sum of four numbers”

You are given an array of n integers, nums, and a target value. Find and return a non-repeating quintuple [nums[a], nums[b], nums[c], nums[d]] that meets all of the following conditions:

  • 0 <= a, b, c, d < n
  • A, B, C and D are different
  • nums[a] + nums[b] + nums[c] + nums[d] == target

You can return the answers in any order.

Example 1: input: nums = (1, 0, 1, 0, 2, 2], target = 0 output: [[,1,2-2-1], [- 2,0,0,2], [1,0,0,1]] example 2: input: Nums = [2,2,2,2], target = 8Copy the code

Two-pointer solution:

Nums [lo] = nums[hi]; nums[hi] = nums[lo] = nums[hi]; So if you want the sum of these two to be bigger, so lo++, if you want the sum of these two to be smaller, so hi–.

NSumTarget = 2Sum 3Sum 4Sum

/** * @param {number[]} nums * @param {number} target * @return {number[][]} */ var fourSum = function (nums, Nums.sort ((a, b) => a-b); / * note: Select * from nums; select * from nums; select * from nums; */ const nSumTarget = (nums, n, start, target) => {let size = nums.length; let res = []; / / at least 2 sum, and the array size should not be less than n if (n < 2 | | size < n) return res; // sum = base case if (n == 2) {let lo = start, hi = size-1; while (lo < hi) { let sum = nums[lo] + nums[hi]; let left = nums[lo], right = nums[hi]; if (sum < target) { while (lo < hi && nums[lo] == left) lo++; } else if (sum > target) { while (lo < hi && nums[hi] == right) hi--; } else { res.push([left, right]); while (lo < hi && nums[lo] == left) lo++; while (lo < hi && nums[hi] == right) hi--; }}} else {for (let I = start; i < size; i++) { let sub = nSumTarget(nums, n - 1, i + 1, target - nums[i]); for (let arr of sub) { arr.push(nums[i]); res.push(arr); } while (i < size - 1 && nums[i] == nums[i + 1]) i++; } } return res; }; Return nSumTarget(nums, 4, 0, target); };Copy the code

Above ~~ will continue to bring two-pointer related topics;

I’m Nuggets Anthony, output exposure input, technical insight into life, goodbye ~