加入收藏
举报
当前仅显示指定条件回帖 [ 展开查看全部 ]
02-14 18:38
#
文件名称:
双指针.md
所在目录:
docs / 算法
文件大小:
10.01 KB
下载地址:
i-want-offer/FE-Essay
   
免责声明:本网站仅提供指向 GitHub 上的文件的链接,所有文件的版权归原作者所有,本网站不对文件内容的合法性、准确性或安全性承担任何责任。
文本预览:
# 双指针
## 思想
顾名思义,使用两个指针进行查找,提高查找效率。
## n数之和
### [两数之和](https://leetcode-cn.com/problems/two-sum/)
> 给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 **两个** 整数,并返回他们的下标。
>
> 你可以假设每种输入只会对应一个答案,但是数组中同一个元素不能使用两次。
```typescript
function twoSum(nums: number[], target: number): number[] {
if (!nums.length) return [];
let num = nums.slice(0);
nums.sort((a, b) => a - b);
let left = 0;
let right = nums.length - 1;
while (left < right) {
if (nums[left] + nums[right] === target) break;
else if (nums[left] + nums[right] < target) {
left++;
} else {
right--;
}
}
left = num.indexOf(nums[left]);
right = // 避免出现 nums[left] === nums[right],从而输出 left === right
num.indexOf(nums[right]) === left
? num.indexOf(nums[right], left + 1)
: num.indexOf(nums[right]);
return [left, right];
}
```
### [三数之和](https://leetcode-cn.com/problems/3sum/)
> 给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c,使得 `a + b + c = 0`。请你找出所有满足条件的不重复的三元组。
```typescript
function threeSum(nums: number[]): number[][] {
if (nums.length < 3) return [];
nums.sort((a, b) => a - b);
const res: number[][] = [];
if (nums[0] > 0) return res; // 如果第一个数大于0,没必要找了
for (let i = 0; i < nums.length; i++) {
if (i && nums[i] === nums[i - 1]) continue; // 去重
let left = i + 1;
let right = nums.length - 1;
while (left < right) {
if (nums[i] + nums[left] + nums[right] === 0) {
res.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 (nums[left] + nums[right] + nums[i] > 0) {
right--;
} else {
left++;
}
}
}
return res;
}
```
### [最接近的三数之和](https://leetcode-cn.com/problems/3sum-closest/)
> 给定一个包含 n 个整数的数组 nums 和一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和,假定每组输入只存在唯一答案。
```typescript
// 思路比较相似,但需要两个变量,一个更新答案,一个更新最小差值
function threeSumClosest(nums: number[], target: number): number {
if (!nums.length) return 0;
let res = Infinity;
let min = Infinity;
nums.sort((a, b) => a - b);
for (let i = 0; i < nums.length; i++) {
let left = i + 1;
let right = nums.length - 1;
while (left < right) {
const current = Math.abs(nums[i] + nums[left] + nums[right] - target);
min = Math.min(min, current);
if (min === current) {
res = nums[i] + nums[left] + nums[right];
}
if (nums[i] + nums[left] + nums[right] < target) {
left++;
} else if (nums[i] + nums[left] + nums[right] > target) {
right--;
} else break;
}
}
return res;
}
```
## 雨水、容器类问题
### [盛最多水的容器](https://leetcode-cn.com/problems/container-with-most-water/)
>给你 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。
>
>说明:你不能倾斜容器,且 n 的值至少为 2。
>
>![img](https://aliyun-lc-upload.oss-cn-hangzhou.aliyuncs.com/aliyun-lc-upload/uploads/2018/07/25/question_11.jpg)
```typescript
function maxArea(heights: number[]): number {
let area = 0;
let left = 0;
let right = heights.length - 1;
while (left < right) {
const width = right - left;
const height = Math.min(heights[left], heights[right]);
area = Math.max(area, width * height);
if (heights[left] < heights[right]) left++;
else right--;
}
return area;
}
```
### [接雨水](https://leetcode-cn.com/problems/trapping-rain-water/)
> 给定 *n* 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
>
> ![img](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/10/22/rainwatertrap.png)
```typescript
function trap(heights: number[]): number {
let left = 0;
let right = heights.length - 1;
let leftMax = 0;
let rightMax = 0;
let total = 0;
while (left < right) {
if (heights[left] < heights[right]) {
heights[left] < leftMax
? (total += leftMax - heights[left])
: (leftMax = heights[left]);
left++;
} else {
heights[right] < rightMax
? (total += rightMax - heights[right])
: (rightMax = heights[right]);
right--;
}
}
return total;
}
```
### [长度最小的子数组](https://leetcode-cn.com/problems/minimum-size-subarray-sum/)
> 给定一个含有 n 个正整数的数组和一个正整数 s,找出该数组中满足其和 >= s 的长度最小的连续子数组,并返回其长度。如果不存在符合条件的连续子数组,返回 0
```typescript
function minSubArrayLen(s: number, nums: number[]): number {
let i = 0
let answer = Number.MAX_SAFE_INTEGER
let sum = 0

for(let j = 0; j < nums.length; j++) {
const num = nums[j]
sum += num
while(sum >= s) {
answer = Math.min(answer, j - i + 1)
sum -= nums[i++]
}
}

return answer === Number.MAX_SAFE_INTEGER ? 0 : answer
}
```
## 链表类
### [删除链表的倒数第 n 个节点](https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/)
> 给定一个链表,删除链表的倒数第 *n* 个节点,并且返回链表的头结点。
```typescript
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
const listNode = new ListNode(null)
listNode.next = head

let len = 0
let temp = head

while(temp) {
temp = temp.next
len++
}

len -= n
temp = listNode

while(len) {
len--
temp = temp.next
}

temp.next = temp.next.next
return listNode.next
}
```
### [回文链表](https://leetcode-cn.com/problems/palindrome-linked-list/)
> 请判断一个链表是否为回文链表。
```typescript
function isPalindrome(head: ListNode): boolean {
if(!head) return true
let pre: ListNode = null
let temp: ListNode
let fast = head
let slow = head

while(fast && fast.next) {
fast = fast.next.next
// 反转链表
temp = slow
slow = slow.next
temp.next = pre
pre = temp
}
if(fast) slow = slow.next
while(pre && slow) {
if(pre.val !== slow.val) return false
pre = pre.next
slow = slow.next
}
return true
}
```
### [环形链表](https://leetcode-cn.com/problems/linked-list-cycle/)
> 给定一个链表,判断链表中是否有环。
>
> 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。
```javascript
function hasCycle(head) {
while(head) {
if(head.flag) return true
head.flag = true
head = head.next
}
return false
}
```
js 简便方法
```js
function hasCycle(head) {
try {
JSON.stringify(head)
return false
} catch {
return true
}
}
```
### [返回倒数第 k 个节点](https://leetcode-cn.com/problems/kth-node-from-end-of-list-lcci/)
> 实现一种算法,找出单向链表中倒数第 k 个节点。返回该节点的值。
```js
function kthToLast(head, k) {
if(!head || !k) return null
let fast = head
let slow = head

while(k--) {
if(!fast) return null
fast = fast.next
}

while(fast) {
fast = fast.next
slow = slow.next
}
return slow.val
}
```
### [合并两个排序链表](https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/)
> 输入两个递增排序的链表,合并这两个链表使新链表的节点仍然是递增排序的。
```typescript
function mergeTwoLists(l1: ListNode, l2: ListNode): ListNode {
if(!l1) return l2
else if(!l2) return l1

if(l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2)
return l1
} else {
l2.next = mergeTwoLists(l2.next, l1)
return l2
}
}
```
### [两个链表的第一个公共节点](https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/)
> 输入两个链表,找出他们的第一个公共节点
```typescript
function getIntersectionNode(headA: ListNode, headB: ListNode): ListNode {
let p1 = headA
let p2 = headB

while(p1 !== p2) {
p1 = p1 === null ? headB : p1.next
p2 = p2 === null ? headA : p2.next
}

return p1
}
```
### [环形链表II](https://leetcode-cn.com/problems/linked-list-cycle-ii/)
> 给定一个链表,返回链表开始入环的第一个节点。如果链表无环,则返回 null。
```typescript
function detectCycle(head: ListNode): ListNode {
if(!head || !head.next) return null
let fast = head.next.next
let slow = head.next
let p1 = head

while(fast !== null && fast !== slow) {
if(fast.next) fast = fast.next.next
else fast = null
slow = slow.next
}

if(fast === null) return null
else {
while(p1 !== slow) {
p1 = p1.next
slow = slow.next
}
return slow
}
}
```
## 字符串类
### [验证回文串](https://leetcode-cn.com/problems/valid-palindrome/)
> 给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。
```typescript
function isPalindrome(s: string): boolean {
s = s.replace(/[^0-9a-zA-Z]/g, '').toLocaleLowerCase()
let left = 0
let right = s.length - 1

while(left < right) {
if(s[left] !== s[right]) return false
left++
right--
}
return true
}
```
点赞 回复
回帖
支持markdown部分语法 ?