双指针解决数组问题（python）

1、快慢指针

快慢指针，常用于原地修改数组

删除有序数组中的重复项

def removeDup(nums):
	slow, fast = 0, 1
	while fast < len(nums):
		if nums[slow] != nums[fast]:
			slow += 1
			nums[slow] = nums[fast]
		fast += 1
	return slow+1
	# nums[:slow+1]
1
2
3
4
5
6
7
8
9

给定一个已排序的链表，删除所有重复的元素，返回删除后的链表

def removeDupList(head):
	if not head: return None
	p1, p2 = head, head
	while p2:
		if p1.val != p2.val:
			p1.next = p2
			p1 = p1.next
		p2 = p2.next
	p1.next = None
	return head
1
2
3
4
5
6
7
8
9
10

移除元素

原地移除所有数值等于val的元素，并返回移除后数组的新长度

def removeK(nums, k):
	if len(nums) == 0: return 0
	slow, false = 0, 0
	while fast < len(nums):
		if nums[fast] != val:
			nums[slow] = nums[fast]
			slow+=1
		fast += 1
	return slow
1
2
3
4
5
6
7
8
9

移动零

给定一个数组，将所有0移动到数组的末尾，同时保持非零元素的相对顺序。

def removeZero(nums):
	n = len(nums)
	slow, fast = 0, 0
	while fast < n:
		if nums[fast] != 0:
			nums[slow] = nums[fast]
			slow += 1
		fast += 1
	while slow < n:
		nums[slow] = 0
		slow += 1
1
2
3
4
5
6
7
8
9
10
11

2、左右指针

只要数组有序，就应该想到双指针技巧

二分查找

在有序列表中查找目标值所在位置

def binarySearch(nums, target):
	left = 0
	right = len(nums)-1
	while left <= right:
		mid = (right-left)//2
		if nums[mid]==terget:
			return mid
		elif nums[mid] < target:
			left = mid+1
		else:
			right = mid-1
	return -1
1
2
3
4
5
6
7
8
9
10
11
12

两数之和

数组有序，从数组中找出满足相加之和等于目标值的两个数

def twoSum(nums, target):
	left, right = 0, len(nums)-1
	while left != right:
		s = nums[left]+nums[fast]
		if s == target:
			return [left+1, right+1]
		elif s > target:
			right -= 1
		else:
			left += 1
	return [-1, -1]
1
2
3
4
5
6
7
8
9
10
11

反转数组

# 方法一：切片的方式，字符串和数组都可以使用切片的方式反转
a = [1,2,3,4]
b = a[::-1]    # b=[4,3,2,1]
# 方法二：reverse()，只有列表有reverse()
a.reverse()   # a=[4,3,2,1]
# 方法三：左右指针
def reverseList(nums):
	left, right = 0, len(nums)-1
	while left < right:
		temp = nums[right]
		nums[right] = nums[left]
		nums[left] = temp
		left+=1
		right-=1
1
2
3
4
5
6
7
8
9
10
11
12
13
14

最长回文子串

找回文串的难点在于，回文串的长度可能是奇数，也可能是偶数。解决该问题的核心是从中心向两端扩散的双指针技巧。
如果回文串的长度为奇数，则有一个中心字符；如果回文串的长度为偶数，则可认为它有两个中心字符。

def palindrome(s, l, r):
	 while l>=0 and r<len(s) and s[l] == s[r]:
	 	l-=1
	 	r+=1
	 return s[l+1:r]
def longestPalindrome(s):
	res = ''
	for i in range(len(s)):
		s1 = palindrome(s, i, i)
		s2 = palindrome(s, i, i+1)
		res = res if res > len(s1) else s1
		res = res if res > len(s2) else s2
	return res
1
2
3
4
5
6
7
8
9
10
11
12
13