【LeetCode】Summary of Two Pointer Problems

【LeetCode】Two-pointer problem solving summary

写在前面

这里是小飞侠Pan🥳,立志成为一名优秀的前端程序媛！！！

本篇文章同时收录于我的github前端笔记仓库中,持续更新中,欢迎star~

https://github.com/mengqiuleo/myNote

11. 盛最多水的容器

11. 盛最多水的容器

给定一个长度为 n 的整数数组 height .有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) ,找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水.

返回容器可以储存的最大水量.

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7].在此情况下,容器能够容纳水（表示为蓝色部分）的最大值为 49.

示例 2：

输入：height = [1,1]
输出：1

题解思路

• 使用双指针,The left and right pointers point to the beginning and end of the array, respectively
• The capacity of the left and right pointers is calculated each time,Then gradually move the pointer towards the middle,直到两个指针相遇
• If the height of the left pointer is less than the height of the right pointer,Then move the left pointer.反之亦然.

var maxArea = function(height) {
    
    let left = 0, right = height.length - 1;
    let ans = 0;
    while(left < right){
    
        let area = Math.min(height[left],height[right])*(right - left); //Calculate the capacity each time
        ans = Math.max(ans,area);//更新最大值
        if(height[left] <= height[right]){
    
            left++;
        }else{
    
            right--;
        }
    }
    return ans;
};

15. 三数之和

15. 三数之和

给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组.

注意：答案中不可以包含重复的三元组.

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

示例 2：

输入：nums = []
输出：[]

示例 3：

输入：nums = [0]
输出：[]

题解思路

• 首先对数组进行排序
• Fix a first number,Then the last two numbers use double pointers,Because the array is in order at this time,So if and greater than0,Then move the right pointer to the left.
• 另外,in the loop each time the first pointer is pinned,We can perform pruning operations
  • If the same number is encountered,直接continue
  • If the fixed first number is greater than0,直接break跳出循环,因为数组是有序的,The latter number must be greater than the former,Then it can never be0

var threeSum = function(nums) {
    
    let ans = [];
    const len = nums.length;
    if(len < 3) return ans;
    nums.sort((a,b) => a - b);
    for(let i = 0; i < len; i++){
    
        if(nums[i] > 0) break;
        if(i > 0 && nums[i] == nums[i-1]) continue;
        let left = i + 1;
        let right = len - 1;
        while(left < right){
    
            let sum = nums[i] + nums[left] + nums[right];
            if(sum === 0){
    
                ans.push([nums[i],nums[left],nums[right]]);
                while(left < right && nums[left] === nums[left + 1]) left++;
                while(left < right && nums[right] === nums[right - 1]) right--;
                left++;
                right--;
            }
            else if(sum < 0) left++;
            else if(sum > 0) right--;
        }
    }
    return ans;
};

16. 最接近的三数之和

16. 最接近的三数之和

给你一个长度为 n 的整数数组 nums 和 一个目标值 target.请你从 nums 中选出三个整数,使它们的和与 target 最接近.

返回这三个数的和.

假定每组输入只存在恰好一个解.

示例 1：

输入：nums = [-1,2,1,-4], target = 1
输出：2

解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) .
示例 2：

输入：nums = [0,0,0], target = 1
输出：0

题解思路

• Similar to question 15,Also fixed the first number,Double pointer points to the next number and the last number
• 首先需要对数组进行排序
• 用变量resto store the final answer
• Compare the current absolute sum each timeresdecision value in ,并更新结果
• 如果相同,就返回,No need to compare anymore

var threeSumClosest = function(nums, target) {
    
    let res = Number.MAX_SAFE_INTEGER;
    nums.sort((a,b) => a - b);
    let len = nums.length;
    for(let i = 0; i < len; i++){
    
        let left = i + 1, right = len - 1;
        while(left < right){
    
            let sum = nums[i] + nums[left] + nums[right];
            if(Math.abs(sum - target) < Math.abs(res - target)){
    
                res = sum;
            }
            if(sum < target){
    
                left++;
            }else if(sum > target){
    
                right--;
            }else{
    
                return sum;
            }
        }
    }
    return res;
};

18. 四数之和

18. 四数之和

给你一个由 n 个整数组成的数组 nums ,和一个目标值 target .请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应,则认为两个四元组重复）：

• 0 <= a, b, c, d < n
• a、b、c 和 d 互不相同
• nums[a] + nums[b] + nums[c] + nums[d] == target

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

题解思路

• Loop over the first two numbers,The last two numbers use double pointers

• 首先对数组排序

• 可以进行剪枝：

  • if(i > 0 && nums[i] === nums[i-1]) continue;
    //If the current minimum sum is greater than the target value,那就结束循环,因为数组有序,The latter sum must be larger
    if(nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target) break;
    //If the current maximum sum is smaller than the target value,Then just skip the number to be looped
    if(nums[i] + nums[len-1] + nums[len-2] + nums[len-3] < target) continue;
    

• 在while循环中,要根据sum和target的大小,左右移动指针,And because the same number can appear,So exclude the same numbers

  • while(left < right){
            
    	if(nums[left] !== nums[++left]) break;
    }
    

完整代码

var fourSum = function(nums, target) {
    
  let res = [];
  let len = nums.length;
  if(len < 4) return [];
  nums.sort((a,b) => a - b);
  for(let i = 0; i < len - 3; i++){
    
    if(i > 0 && nums[i] === nums[i-1]) continue;
    if(nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target) break;
    if(nums[i] + nums[len-1] + nums[len-2] + nums[len-3] < target) continue;
    for(let j = i + 1; j < len - 2; j++){
    
      if(j > i + 1 && nums[j] === nums[j-1]) continue;
      if(nums[i] + nums[j] + nums[j+1] + nums[j+2] > target) break;
      if(nums[i] + nums[j] + nums[len-1] + nums[len-2] < target) continue;
      let left = j+1, right = len-1;
      while(left < right){
    
        let sum = nums[i] + nums[j] + nums[left] + nums[right];
        if(sum === target){
    
          res.push([nums[i], nums[j], nums[left], nums[right]]);
          while(left < right && nums[left] === nums[left+1]){
    
            left++;
          }
          while(left < right && nums[right] === nums[right-1]){
    
            right--;
          }
          left++;
          right--;
        } else if(sum > target){
    
          while(left < right){
    
            if(nums[right] !== nums[--right]) break;
          }
        } else if(sum < target){
    
          while(left < right){
    
            if(nums[left] !== nums[++left]) break;
          }
        }
      } 
    }
  }
  return res;
};

42. 接雨水

42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水.

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水（蓝色部分表示雨水）. 

示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

题解思路

• Here we find the rainwater in each column,Finally add up the rain for each column

• for the current requirement for this column,设两个指针,Go both ways from the current column,Find the highest column on both sides

• 此时就要分情况讨论

  • When the column being sought is the shortest,此时就可以计算

    

  • When the column being sought is not the shortest,Then it can't hold water

    

    

var trap = function(height) {
    
    let sum = 0;
    for(let i = 0; i < height.length; i++){
    //遍历每一列,Find the amount of water that can be stored in each column
        if(i == 0 || i == height.length - 1) continue; //Skip the leftmost and rightmost columns
        let lHeight = height[i], rHeight = height[i];
        for(let r = i + 1; r < height.length; r++){
    //右边的指针
            if(height[r] > rHeight) rHeight = height[r];//Get the highest column on the right
        }
        for(let l = i - 1; l >= 0; l--){
    
            if(height[l] > lHeight) lHeight = height[l];//Get the highest column on the left
        }
        let h = Math.min(lHeight,rHeight) - height[i];//Calculates the difference between the minimum value of the columns on both sides and the required current column
        if(h > 0) sum += h;//当差值大于0,That is, the currently required column is the shortest
    }
    return sum;
};

167. 两数之和 II - 输入有序数组

167. 两数之和 II - 输入有序数组

给你一个下标从 1 开始的整数数组 numbers ,该数组已按 非递减顺序排列 ,请你从数组中找出满足相加之和等于目标数 target 的两个数.如果设这两个数分别是 numbers[index1] 和 numbers[index2] ,则 1 <= index1 < index2 <= numbers.length .

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2.

你可以假设每个输入 只对应唯一的答案 ,而且你 不可以 重复使用相同的元素.

你所设计的解决方案必须只使用常量级的额外空间.

示例 1：

输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 .因此 index1 = 1, index2 = 2 .返回 [1, 2] .

示例 2：

输入：numbers = [2,3,4], target = 6
输出：[1,3]
解释：2 与 4 之和等于目标数 6 .因此 index1 = 1, index2 = 3 .返回 [1, 3] .

示例 3：

输入：numbers = [-1,0], target = -1
输出：[1,2]
解释：-1 与 0 之和等于目标数 -1 .因此 index1 = 1, index2 = 2 .返回 [1, 2] .

题解

• 设置两个指针,Points to the beginning and end of the array
• 因为数组是有序的,Then calculate the sum of the two pointers each time,If the calculated result is too large,Then the right pointer moves to the left…
• 如果相等,Returns the pointer subscript+1

var twoSum = function(numbers, target) {
    
    let i = 0, j = numbers.length - 1;
    while(i < j){
    
        let sum = numbers[i] + numbers[j];
        if(sum > target){
    
            j--;
        }else if(sum < target){
    
            i++;
        }else{
    
            return [i+1,j+1];
        }
    }
};

283. 移动零

283. 移动零

给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序.

请注意 ,必须在不复制数组的情况下原地对数组进行操作.

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

输入: nums = [0]
输出: [0]

题解

• Both pointers point to the beginning of the array
• 实现移动0的思想就是：Point the slow pointer to the end of the newly created array,The fast pointer is responsible for scanning the original array
• If the fast pointer swipes to non0 的数,And the fast and slow pointers do not coincide,Then exchange the number of fast and slow pointers
• 如果快慢指针重合,No exchange is required at this time,Also because this number is not0,Then the slow pointer moves backwards,Indicates that this number is added to a new array

var moveZeroes = function(nums) {
    
    let slow = 0, fast = 0;
    while(fast < nums.length){
    
        if(nums[fast]){
    //Sweep to non0的数
            if(fast !== slow){
    
                let temp = nums[slow];
                nums[slow] = nums[fast];
                nums[fast] = temp;
            }
            slow++;//在这个if条件中,The description has been scanned0的数,那么慢指针+1,Because the slow pointer points to the end of the new array
        }
        fast++;//The fast pointer is responsible for scanning the original array,So every time move backwards
    }
};

344. 反转字符串

344. 反转字符串

编写一个函数,其作用是将输入的字符串反转过来.输入字符串以字符数组 s 的形式给出.

不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题.

示例 1：

输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]

示例 2：

输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

题解

var reverseString = function(s) {
    
    let i = 0, j = s.length - 1;
    let temp = '';
    while(i < j){
    
        temp = s[i];
        s[i] = s[j];
        s[j] = temp;
        i++;
        j--;
    }
};

345. 反转字符串中的元音字母

345. 反转字符串中的元音字母

给你一个字符串 s ,仅反转字符串中的所有元音字母,并返回结果字符串.

元音字母包括 ‘a’、‘e’、‘i’、‘o’、‘u’,且可能以大小写两种形式出现.

示例 1：

输入：s = "hello"
输出："holle"

示例 2：

输入：s = "leetcode"
输出："leotcede"

题解

• 将字符串转换成数组
• Two pointers point to the beginning and the end
• Sets the loop condition to exit when two pointers collide
• 如果 i指针 是元音字母,进入if循环,判断 jWhether the pointer is a vowel,如果是,交换,否则,如果 jPointers are not vowels,j指针左移
• 如果 i指针 不是元音字母,i指针 右移
• Finally, concatenate the array into a string and return it

var reverseVowels = function(s) {
    
    let vowels = ['a','e','i','o','u','A','E','I','O','U'];
    let i = 0, j = s.length - 1;
    let arr = s.split('');
    while(i < j){
    
        if(vowels.includes(arr[i])){
    
            if(vowels.includes(arr[j])){
    
                let temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
                j--;
            }else {
    
                j--;
            }
        }else{
    
            i++;
        }
    }
    return arr.join('');
};

844. 比较含退格的字符串

844. 比较含退格的字符串

给定 s 和 t 两个字符串,当它们分别被输入到空白的文本编辑器后,如果两者相等,返回 true .# 代表退格字符.

注意：如果对空文本输入退格字符,文本继续为空.

示例 1：

输入：s = "ab#c", t = "ad#c"
输出：true
解释：s 和 t 都会变成 "ac".

示例 2：

输入：s = "ab##", t = "c#d#"
输出：true
解释：s 和 t 都会变成 "".

示例 3：

输入：s = "a#c", t = "b"
输出：false
解释：s 会变成 "c",但 t 仍然是 "b".

题解

• Because the title says if it appears#,then the character preceding it backspaces.Then we can traverse the string from back to front,And set the flag edge amount to record whether it is encountered or not#
• 如果遇见#,指针向左移动一位,And record with flag variable
• If a normal character is encountered and the flag variable exists,Then the pointer moves one bit to the left,表示退格,And eliminate the flag variable
• Otherwise if an ordinary character is encountered but there is no flag variable,那就退出循环,Compares the characters pointed to by two pointers

var backspaceCompare = function(s, t) {
    
    let i = s.length - 1, j = t.length - 1;
    let skipS = 0, skipT = 0;//标志变量
    while(i >= 0 || j >= 0){
    
        while(i >= 0){
    
            if(s[i] === '#'){
    
                skipS++;
                i--;
            }else if(skipS > 0){
    
                i--;
                skipS--;
            }else break;
        }
        while(j >= 0){
    
            if(t[j] === '#'){
    
                skipT++;
                j--;
            }else if(skipT > 0){
    
                skipT--;
                j--;
            }else break;
        }
        if(s[i] !== t[j]) return false;
        i--;
        j--;
    }
    return true;
};

881. 救生艇

881. 救生艇

给定数组 people .people[i]表示第 i 个人的体重 ,船的数量不限,每艘船可以承载的最大重量为 limit.

每艘船最多可同时载两人,但条件是这些人的重量之和最多为 limit.

返回 承载所有人所需的最小船数 .

示例 1：

输入：people = [1,2], limit = 3
输出：1
解释：1 艘船载 (1, 2)

示例 2：

输入：people = [3,2,2,1], limit = 3
输出：3
解释：3 艘船分别载 (1, 2), (2) 和 (3)

示例 3：

输入：people = [3,5,3,4], limit = 5
输出：4
解释：4 艘船分别载 (3), (3), (4), (5)

题解

• 注意审题,题目中说明,A boat is allowed to carry a maximum of two people
• Two pointers point to the beginning and the end
• 如果 people[left] + people[right] <= limit ：说明 left 和 right Pointed people can be paired（on the same boat）,此时 left 和 right Take a step in the middle;
• 如果 people[left] + people[right] > limit ：说明 right The person pointed at is too heavy,He should be in a boat alone.即 right Take a step towards the middle（right--）.

按照上面的方式,直到 left 与 right 重合,This completes the task.

• 注意,while循环退出的条件是 left === right,那么此时leftThe person who executes the pointer has not yet taken the boat,Then another boat should be added

var numRescueBoats = function(people, limit) {
    
    if(people.length === 0) return 0;
    people = people.sort((a,b) => a - b);
    let left = 0, right = people.length - 1;
    let nums = 0;
    while(left < right){
    
        if(people[left] + people[right] <= limit){
    
            left++;
            right--;
        }else{
    
            right--;
        }
        nums++;
    }
    if(left === right) nums++;//此时leftThe person who executes the pointer has not yet taken the boat,Then another boat should be added
    return nums;
};

977. 有序数组的平方

977. 有序数组的平方

给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序.

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后,数组变为 [16,1,0,9,100]
排序后,数组变为 [0,1,9,16,100]

示例 2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

题解

• 因为数组有序,Then the square of the numbers on both sides has the largest value,The squared value of the middle number is smaller
• The two pointers point to the beginning and end of the array, respectively,Then find the square,Put the larger value of the comparison into the beginning of the array
• Because the two pointers go to the middle,Then the square value sought should also be getting smaller and smaller,So it should be inserted at the top of the array

var sortedSquares = function(nums) {
    
    let res = [];
    let i = 0, j = nums.length - 1;
    while(i <= j){
    
        let left = Math.abs(nums[i]);
        let right = Math.abs(nums[j]);
        if(right > left){
    
            res.unshift(right * right);
            j--;
        }else{
    
            res.unshift(left * left);
            i++;
        }
    }
    return res;
};