当前位置：首页 > news >正文

算法| ss 双指针

news 来源：原创 2024/5/21 13:49:02

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

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 -1var 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