前端 算法 双指针
三数之和
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function(nums) {
let orderNums = nums.sort((a, b) => a - b);
const result = [];
// 三数之和转变为一个固定数去寻找另外两个数
for(let i = 0; i<= orderNums.length - 3; i++) {
let left = i + 1;
let right = orderNums.length - 1;
while(left < right) {
let count = orderNums[i] + orderNums[left] + orderNums[right];
const array = [orderNums[i], orderNums[left], orderNums[right]]
if(count > 0) {
// 由于orderNums是有序的，通过调整右指针左移 调整变小 寻找下一对
right --
} else if (count < 0) {
//由于orderNums是有序的，通过调整左指针右移 调整变大 寻找下一对
left ++
} else {
// 判断是否已经有了对应的数据，不重复
const have = result.find((item) => {
return item.every((value, index) => value === array[index]);
})
if(!have) {
result.push(array)
}
// 寻找下一对
right--
left ++
}
}
}
return result
};
移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var moveZeroes = function(nums) {
for(let i = 0; i < nums.length - 1; i++) {
for(let j = i + 1;j < nums.length; j++) {
let right = j;
if(nums[i] === 0 && nums[j]!== 0) {
// 交互位置,确保第i位现在不可能为0
[nums[i],nums[j]] = [nums[j],nums[i]]
// 然后指针i可以向右移动拉，跳出本次循环
break
}
}
}
};
盛最多水的容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
/**
* @param {number[]} height
* @return {number}
*/
var maxArea = function(height) {
let maxArea = 0;
let left = 0;
let right = height.length - 1;
for(let i = 0; i < height.length; i++) {
for(let j = i + 1;j < height.length;j++) {
let width = j - i;
// 高度选最小的
let heights = Math.min(height[i], height[j])
const area = width * heights
maxArea = Math.max(maxArea,area)
}
}
return maxArea
};
上面的写法虽然也是双指针i和j不断移动，但移动的方式不够灵活
/**
* @param {number[]} height
* @return {number}
*/
var maxArea = function(height) {
let maxArea = 0;
// 两个指针的位置从距离最远开始，不断靠近
let left = 0;
let right = height.length - 1;
while( left < right) {
const heights = Math.min(height[left], height[right]);
const width = right - left;
const area = heights * width;
maxArea = Math.max(maxArea,area)
// 尽量保留高的值，参与下一轮面积的计算，将值较小的那个指针移动
if(height[right] > height[left]) {
left++
} else {
right--
}
}
return maxArea
};
接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
leetcode 接雨水 https://leetcode.cn/problems/trapping-rain-water/solutions/692342/jie-yu-shui-by-leetcode-solution-tuvc/?envType=study-plan-v2&envId=top-100-liked
对于下标 i，下雨后水能到达的最大高度等于下标 i 两边的最大高度的最小值，下标 i 处能接的雨水量等于下标 i 处的水能到达的最大高度减去 height[i]。
我们可以分别用两个for 循环，求出两部分的面积，然后再对两个数组记录的元素进行比较，取较小的值为一个新数组，最后让这个新数组减去柱子本身的高度。
var trap = function(height) {
let ans = 0;
// 由上图的动态规划可知，两个图加起来，取较低的值为max并减去柱子的高度
// 但如果用双指针来实现更容易，一个从左往右，一个从右往左。
let left = 0, right = height.length - 1;
// 分别记录从左往右的最大值，和从右往左的最大值
let leftMax = 0, rightMax = 0;
while (left < right) {
// 分别记录从左往右的最大值，和从右往左的最大值
leftMax = Math.max(leftMax, height[left]);
rightMax = Math.max(rightMax, height[right]);
// 比较当前两个指针所指的值的大小，始终从小的那边取值
if (height[left] < height[right]) {
ans += leftMax - height[left];
left++;
} else {
ans += rightMax - height[right];
right--;
}
}
return ans;
};
原文地址：https://blog.csdn.net/glorydx/article/details/143510918
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！