数据结构与算法之双指针(一)

1. 两数之和

给定一个已按照升序排列 的有序数组,找到两个数使得它们相加之和等于目标数.
函数应该返回这两个下标值 index1 和 index2,其中 index1 必须小于 index2.

说明:

  • 返回的下标值(index1 和 index2)不是从零开始的.
  • 你可以假设每个输入只对应唯一的答案,而且你不可以重复使用相同的元素.

题解:

两数之和可以借助遍历两次数组的暴力求解方法(时间复杂度位O(n^2)空间复杂度为O(1))或哈希表(时间复杂度为O(n)空间复杂度为O(n))求解. 但是这两种方法都是针对无序数组的, 没有利用到输入数组的有序的性质. 可以借助双指针,我们假设左边的指针指向第一个元素, 右边的指针指向最后一个元素. 每次计算两个指针指向的元素和, 然后同目标值作比较, 如果等于目标值则得到结果, 如果两数的和大于目标值, 则有指针往左移, 否则左指针往右移, 重复以上操作直至找到答案. 使用双指针的实质是缩小查找范围. 双指针的时间复杂度为O(n)空间复杂度为O(1)

代码
Python3

def twoSum(self, nums, target):
  left = 0
  right = len(nums) - 1

  while left < right:
    temp = nums[left] + nums[right]
    if temp == target:
      return [left + 1, right + 1]
    elif temp > target:
      right -= 1
    else:
      left += 1
  return [-1, -1]

JavaScript

function twoSum(nums, target) {
  let left = 0
  let right = nums.length - 1

  while (left < right) {
    let temp = nums[left] + nums[right]
    if (temp === target) {
      return [left + 1, right + 1]
    } else if (temp < target) {
      left++
    } else {
      right--
    }
  }
  return [-1, -1]
}

平方数之和

给定一个非负整数c,你要判断是否存在两个整数a和b,使得a2 + b2 = c

提示:

  • 0 <= c <= 231 - 1

示例:

输入:c = 5
输出:true
解释:1 * 1 + 2 * 2 = 5

输入:c = 3
输出:false

输入:c = 4
输出:true

输入:c = 2
输出:true

输入:c = 1
输出:true

题解:

双指针法. 对于一个整数c, 如果存在a * a + b * b = c, 那么a和b的值必然不大于c的开方. 因此我们可以让a = 0, b = c的开方, 当a <= b时有以下三种情况

  • a * a + b * b = c, 存在返回true
  • a * a + b * b < c, 让a+1
  • a * a + b * b > c, 让b-1

代码:
Python3

def sqrtSum(self, c):
  left = 0
  right = int(c**0.5)

  while left <= right:
    temp = left**2 + right**2
    if temp == c:
      return True
    elif temp < c:
      i += 1
    else:
      j -= 1
  return False

JavaScript

function sqrtSum(c) {
  let left = 0
  let right = Math.floor(Math.sqrt(c))

  while (left <= right) {
    let temp = left * left + right * right
    if (temp === c) {
      return true
    } else if (temp < c) {
      left++
    } else {
      right--
    }
  }
  return false
}

反转字符串中的元音字母

编写一个函数, 以字符串作为输入, 反转该字符串中的元音字母.

提示:

  • 元音字母不包含字母 “y”

示例:

输入:"hello"
输出:"holle"

输入:"hello"
输出:"holle"

题解:

双指针, 左右指针指向的元素为原因字母时停下进行交换, 否则移动指针

代码
Python3

def reverseVowels(self, s):
  left = 0
  right = len(s) - 1
  vowels = set('aoeiuAOEIU')
  s = list(s)

  while left < right:
    if s[left] in vowels and s[right] in vowels:
      s[left], s[right] = s[right], s[left]
      left += 1
      right -= 1
    if not s[left] in vowels:
      left += 1
    if not s[right] in vowels:
      right -= 1
  return ''.join(s)

JavaScript

function reverseVowels(s) {
  let left = 0
  let right = s.length - 1
  let vowels = new Set(['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'])
  let arr = s.split('')

  while (left < right) {
    if (vowels.has(arr[left])) {
      if (vowels.has(arr[right])) {
        [arr[left], arr[right]] = [arr[right], arr[left]]
        left++
      }
      rigth--
    } else {
      left++
    }
  }
  return arr.join('')
}

验证回文字符串

给定一个非空字符串s, 最多删除一个字符. 判断是否能成为回文字符串.

提示:

  • 字符串只包含从 a-z 的小写字母. 字符串的最大长度是50000.

示例:

输入: "aba"
输出: True

输入: "abca"
输出: True
解释: 你可以删除c字符

题解

通常情况下判断是否是回文字符串我们可以让左右指针同时移动然后判断指针位置上的元素是否相同即可得到是否是回文字符串, 但是题目中最多可以删除一个字符串那么我们可以在判断左右指针上的元素不相等时删除一个元素然后在进行对比即可

代码
Python3

def validPalindrome(self, s):
  left = 0
  right = len(s) - 1

  while left <= right:
    if s[left] == s[right]:
      left += 1
      right -= 1
    else:
      x = s[left : right]
      y = s[left+1 : rigth+1]
      return True if x[::-1] == x or y[::-1] == y else False
  return True

JavaScript

function validPalindrome(s) {
  let left = 0
  let right = s.length - 1

  while (left < right) {
    if (s[left] !== s[right]) {
      return isPali(s, left + 1, right) || isPali(s, left, right - 1)
    }
    left++
    right--
  }
  return true
}

function isPali(s, l, r) {
  while (l < r) {
    if (s[l] !== s[r]) {
      return false
    }
    l++
    r--
  }
  return true
}

合并两个有序数组

合并两个有序数组

是否为环形链表

是否是环形链表