双指针

思想

顾名思义，使用两个指针进行查找，提高查找效率。

n数之和

两数之和 (opens new window)

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的下标。

你可以假设每种输入只会对应一个答案，但是数组中同一个元素不能使用两次。

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];
}

三数之和 (opens new window)

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c，使得 a + b + c = 0。请你找出所有满足条件的不重复的三元组。

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;
}

最接近的三数之和 (opens new window)

给定一个包含 n 个整数的数组 nums 和一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和，假定每组输入只存在唯一答案。

// 思路比较相似，但需要两个变量，一个更新答案，一个更新最小差值
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;
}

雨水、容器类问题

盛最多水的容器 (opens new window)

给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

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;
}

接雨水 (opens new window)

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

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;
}

长度最小的子数组 (opens new window)

给定一个含有 n 个正整数的数组和一个正整数 s，找出该数组中满足其和 >= s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的连续子数组，返回 0

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 个节点 (opens new window)

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

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
}

回文链表 (opens new window)

请判断一个链表是否为回文链表。

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
}

环形链表 (opens new window)

给定一个链表，判断链表中是否有环。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

function hasCycle(head) {
  while(head) {
    if(head.flag) return true
    head.flag = true
    head = head.next
  }
  return false
}

js 简便方法

function hasCycle(head) {
  try {
    JSON.stringify(head)
    return false
  } catch {
    return true
  }
}

返回倒数第 k 个节点 (opens new window)

实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。

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
}

合并两个排序链表 (opens new window)

输入两个递增排序的链表，合并这两个链表使新链表的节点仍然是递增排序的。

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
  }
}

两个链表的第一个公共节点 (opens new window)

输入两个链表，找出他们的第一个公共节点

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 (opens new window)

给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

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
  }
}

字符串类

验证回文串 (opens new window)

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

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
}