算法| ss 双指针

时间：2024-04-07 12:44:46
  • 11.盛水最多的容器
  • 15.三数之和
  • 26.删除有序数组中的重复项
  • 27.移除元素
  • 75.颜色分类
  • 88.合并两个有序数组
  • 167.两数之和2-输入有序数组
    1. 最短无序连续子数组
    1. 追加字符以获得子序列

11.盛水最多的容器

/**
 * @param {number[]} height
 * @return {number}
 */
// 思路
// 左0 右 n-1
// while left<right
// 计算宽度right-left
// 左边大： 右高乘以width  右--
// 右边大： 左高乘以width 左++
// 指针移动： 谁小谁移动
// 更新最大值
var maxArea = function (height) {
  let left = 0;
  let right = height.length - 1;
  let ans = 0;
  while (left < right) {
    let width = right - left;
    if (height[left] > height[right]) {
      val = width * height[right];
      ans = Math.max(ans, val);
      right -= 1;
    } else {
      val = width * height[left];
      ans = Math.max(ans, val);
      left += 1;
    }
  }
  console.log(ans);
};
maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]);
// 输入：[1,8,6,2,5,4,8,3,7]
// 输出：49

15.三数之和

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
// 思路
//  数组升序（很重要）
// 计算公式：  定个首元素  +  左元素 + 右元素 = 0
// for循环定义首元素
// while循环 变更左右指针， 确定左右元素
// total <0 left++  total> 0 rigth++
// total==0 更新结果， 并且剪枝 如果左==左+1  左++   右=右-1 右--
var threeSum = function (nums) {
  nums.sort((a, b) => a - b);
  let ans = [];
  for (let i = 0; i < nums.length; i++) {
    let startNum = nums[i];
    let left = i + 1;
    let right = nums.length - 1;
    if (startNum > 0) continue;
    if (i > 0 && startNum === nums[i - 1]) continue;
    while (left < right) {
      let total = startNum + nums[left] + nums[right];
      if (total < 0) {
        left += 1;
      } else if (total > 0) {
        right -= 1;
      } else {
        ans.push([startNum, nums[left], nums[right]]);
        // 剪枝避免重复元素
        while (left < right && nums[left] === nums[left + 1]) left += 1;
        while (left < right && nums[right] === nums[right - 1]) right -= 1;
        left += 1;
        right -= 1;
      }
    }
  }
  //   console.log("ans", ans);
  return ans;
};
// [ -4, -1, -1, 0, 1, 2 ]
threeSum([-1, 0, 1, 2, -1, -4]);

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

26.删除有序数组中的重复项

/**
 * @param {number[]} nums
 * @return {number}
 */
// 思路
// 双指针解法
// for循环 right从1开始
// 当left right对应的值不相等时， left递增1， 并且对应值赋值为right对应的值
var removeDuplicates = function (nums) {
  let left = 0;
  for (let right = 1; right < nums.length; right++) {
    if (nums[left] !== nums[right]) {
      left += 1;
      nums[left] = nums[right];
    }
  }
  console.log(left + 1);
  return left + 1;
};
removeDuplicates([0, 0, 1, 1, 1, 2, 2, 3, 3, 4]);

27.移除元素

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
// 思路
// 双指针解法
// for遍历数组
// 条件: 当遍历值不等于val时, 设置num[i]为遍历值，并指针右移
// 都是不利用任何api，只是更改数组下标的方式得到结果
var removeElement = function (nums, val) {
  let i = 0;
  for (let j = 0; j < nums.length; j++) {
    if (nums[j] !== val) {
      nums[i] = nums[j];
      i += 1;
    }
  }
  return i;
};
removeElement([3, 2, 2, 3], 3);
// nums = [3,2,2,3], val = 3

75.颜色分类

88.合并两个有序数组

/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
// 思路
// 定义两个数组的尾指针
// whiile 循环比较尾指针值大小
// 分别填充比较后的数值， 指针左移
// for循环nums2  填充， 补充前面的数据（针对num2的长度比num1长）
var merge = function (nums1, m, nums2, n) {
  let firstPoint = m - 1;
  let secondPoint = n - 1;
  //   倒序 从尾部比较2个数组，填充， 指针左移
  while (firstPoint >= 0 && secondPoint >= 0) {
    if (nums1[firstPoint] > nums2[secondPoint]) {
      nums1[firstPoint + secondPoint + 1] = nums1[firstPoint];
      firstPoint -= 1;
    } else {
      nums1[firstPoint + secondPoint + 1] = nums2[secondPoint];
      secondPoint -= 1;
    }
  }
  //   num1比num2短的情况下
  if (secondPoint >= 0) {
    for (let i = 0; i < secondPoint; i++) {
      nums1[i] = nums2[i];
    }
  }
};

// 输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
// 输出：[1,2,2,3,5,6]
// 解释：需要合并 [1,2,3] 和 [2,5,6] 。
// 合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

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

581. 最短无序连续子数组

/**
 * @param {number[]} nums
 * @return {number}
 */
// 思路： 双指针解法
// while循环 从左 从右遍历 找到 left right边界
// for循环left right 找到其中的最大值 最小值
// 确定左右指针的最终位置， left比min小  max 比right小
// 更新结果 right-left -1

var findUnsortedSubarray = function (nums) {
  let len = nums.length;
  let left = 0;
  let right = len - 1;
  while (left < len && nums[left] <= nums[left + 1]) left++;
  while (right >= 0 && nums[right - 1] <= nums[right]) right--;
  let min = Infinity;
  let max = -Infinity;
  for (let i = left; i <= right; i++) {
    min = Math.min(min, nums[i]);
    max = Math.max(max, nums[i]);
  }
  while (nums[left] > min) left--;
  while (nums[right] < max) right++;
  console.log(left, right);
  return left < right ? right - left - 1 : 0;
};
console.log(findUnsortedSubarray([2, 6, 4, 8, 10, 9, 15]));
console.log(findUnsortedSubarray([1, 3, 2, 2, 2]));
// 输入：nums = [2,6,4,8,10,9,15]
// 输出：5

2486. 追加字符以获得子序列

/**
 * @param {string} s
 * @param {string} t
 * @return {number}
 */
// 思路
// 双指针解法
// 遍历字符串s , 如果s某个字符等于t的某个字符，则i++
// 更新结果n-i
var appendCharacters = function (s, t) {
  const n = t.length;
  let i = 0;
  for (let j = 0; j < s.length; j++) {
    if (s[j] === t[i]) {
      i++;
    }
  }
  console.log(n - i);
  return n - i;
};
appendCharacters("coaching", "coding");
// 输入：s = "coaching", t = "coding"
// 输出：4

相关文章