双指针

第 167 题

var twoSum = function (numbers, target) {
  // 定义数组头尾双指针
  let i = 0
  let j = numbers.length - 1
  // 判断当前值与双指针值和的大小
  while (numbers[i] + numbers[j] !== target) {
    if (numbers[i] + numbers[j] > target) {
      // 超过右指针左移
      j--
    }
    if (numbers[i] + numbers[j] < target) {
      // 不足左指针右移
      i++
    }
  }
  // 返回符合结果值的位置
  return [i + 1, j + 1]
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

第 633 题

平方数之和open in new window

var judgeSquareSum = function (c) {
  // 定义双指针，右指针为目标数平方根取整
  let i = 0
  let j = parseInt(Math.sqrt(c))
  // 返回值
  let result = false
  // 左指针小于右指针的时候循环
  // <= 处理特殊用例 2
  while (i <= j) {
    // 发现符合条件跳出循环
    if (i * i + j * j === c) {
      result = true
      break
    }
    // 超过右指针左移
    if (i * i + j * j > c) {
      j--
    }
    // 不足左指针右移
    if (i * i + j * j < c) {
      i++
    }
  }
  return result
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

第 345 题

反转字符串中的元音字母open in new window

var reverseVowels = function (s) {
  // 定义双指针
  let i = 0
  let j = s.length - 1
  // 字符串转数组，定义元音字母Set类型
  let arr = s.split('')
  let res = new Set(['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'])
  while (i < j) {
    // 利用Set类型has判断是否两个指针都为元音字符
    // 都为元音字符时交换两个元音字符，并移动指针
    if (res.has(arr[i]) && res.has(arr[j])) {
      let mid = arr[i]
      arr[i] = arr[j]
      arr[j] = mid
      i++
      j--
    }
    // 左指针不为元音字符，右移
    if (!res.has(arr[i])) {
      i++
    }
    // 右指针不为元音字符，左移
    if (!res.has(arr[j])) {
      j--
    }
  }
  // 返回合并值
  return arr.join('')
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

第 88 题

合并两个有序数组open in new window

var merge = function (nums1, m, nums2, n) {
  // 定义双指针为两个数组的末尾，则总共需要处理的位数为p
  let i = m - 1
  let j = n - 1
  let p = i + j + 1
  while (p >= 0) {
    // 当两个数组都还有元素未处理时，判断元素大小
    if (i >= 0 && j >= 0) {
      // 将较大的数放在p位置，并移动相应指针，p位置左移。
      if (nums1[i] < nums2[j]) {
        nums1[p--] = nums2[j--]
      } else {
        nums1[p--] = nums1[i--]
      }
    }
    // 左指针已经没有元素时，直接将右指针元素放在p位置
    if (i < 0 && j >= 0) {
      nums1[p--] = nums2[j--]
    }
    // 右指针已经没有元素时，直接将左指针元素放在p位置
    if (i >= 0 && j < 0) {
      nums1[p--] = nums1[i--]
    }
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

第 141 题

环形链表open in new window

var hasCycle = function (head) {
  // 处理链表为空或只有一个节点的情况
  if (!head || !head.next) {
    return false
  }
  // 定义快慢指针
  let l1 = head
  let l2 = head.next
  // 快慢指针所指向的节点都存在时进行循环
  while (l1 && l2 && l2.next) {
    if (l1 === l2) {
      return true
    }
    // 快指针每次前进两个节点，如果存在环，快指针必然将绕圈之后追上慢指针
    l1 = l1.next
    l2 = l2.next.next
  }
  return false
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

第 524 题

通过删除字母匹配到字典里最长单词open in new window

var findLongestWord = function (s, d) {
  // 将传入的数组按字典序排序
  let arr = d.sort()
  // 分割传入的字符串为数组
  let sArr = s.split('')
  // 定义返回值
  let str = ''
  // 对匹配数组的每一项都进行遍历
  for (let i = 0; i < arr.length; i++) {
    // 将当前项拆分为数组，定义当前满足条件子字符串的长度k
    let item = arr[i].split('')
    let k = 0
    // 对字符逐个匹配，匹配成功时k指针右移
    for (let p = 0; p < sArr.length; p++) {
      if (sArr[p] === item[k]) {
        k++
      }
    }
    // k值等于当前单词的长度时表示当前单词匹配成功
    // 在大于之前匹配成功的单词长度时更新单词
    if (k === item.length && k > str.length) {
      str = arr[i]
    }
  }
  return str
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

# 双指针

# 第 167 题

# 第 633 题

# 第 345 题

# 第 88 题

# 第 141 题