双指针应用

#同向：不改变元素的相对位置

#反向：改变元素的相对位置

例一：翻转数组，不额外开辟空间O(1)

[1,2,3,4,5,6,7,8] → [8,7,6,5,4,3,2,1]

#反向

1 def reverseArray(s):
2     i, j = 0, len(s) - 1
3     while i < j:
4         s[i], s[j] = s[j], s[i]
5         i += 1
6         j -= 1
7     return s

例二：将数组所有的元素0移动到数组一端

[0,1,2,0,3,0,0,5,0] → [1, 2, 3, 5, 0, 0, 0, 0, 0]
#同向

 1 def moveEnd(s):
 2     i, j = 0 ,1
 3     while i < j and j <= len(s)-1:
 4         if s[i] == 0 and s[j] != 0:
 5             s[i], s[j] = s[j], s[i]
 6         while s[i] != 0:
 7             i += 1
 8             j += 1
 9         while j <= len(s)-1 and (s[i] == 0 and s[j] == 0):
10             j += 1
11     return s

#反向

 1 def moveEnd(s):
 2     i, j = 0 ,len(s) - 1
 3     while i < j:
 4         if s[i] == 0 and s[j] != 0:
 5             s[i], s[j] = s[j], s[i]
 6         while (i < j) and (s[i] != 0):
 7             i += 1
 8         while (i < j) and (s[j] == 0):
 9             j -= 1       
10     return s

例三：将数组的奇数与偶数分开

[2,7,6,1,3,4,5,2,8] → [5, 7, 3, 1, 6, 4, 2, 2, 8]
#同向

 1 def exchange(nums):
 2 
 3     i, j = 0, 1
 4     while i < j and j <= len(nums) - 1:
 5         if nums[i] & 1 == 0 and nums[j] & 1 == 1:
 6             nums[i], nums[j] = nums[j], nums[i]
 7         while nums[i] & 1 == 1:
 8             i += 1
 9             j += 1
10         while (j <= len(nums) - 1) and nums[j] & 1 == 0:
11             j += 1
12 
13     return nums


#反向

 1 def exchange(nums):
 2 
 3     i, j = 0, len(nums) - 1
 4     while i < j:
 5         if nums[i] & 1 == 0 and nums[j] & 1 == 1:
 6             nums[i], nums[j] = nums[j], nums[i]
 7         while nums[i] & 1 == 1:
 8             i += 1
 9             j -= 1
10         while (j <= len(nums) - 1) and nums[j] & 1 == 0:
11             j -= 1
12 
13     return nums