two pointer problems
Two Sum III - Data structure design
Design and implement a TwoSum class. It should support the following operations: add and find.
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
def __init__(self):
self.num = {}
"""
@param number: An integer
@return: nothing
"""
def add(self, number):
if number not in self.num:
self.num[number] = 0
self.num[number]+=1
"""
@param value: An integer
@return: Find if there exists any pair of numbers which sum is equal to the value.
"""
def find(self, value):
for i in self.num.keys():
target = value - i
if target in self.num:
if target != i:
return True
else:
if self.num[i] > 1:
return True
return FalseMove Zeroes
Given an array nums, write a function to move all 0’s to the end of it while maintaining the relative order of the non-zero elements.
2
3
4
5
6
7
8
9
10
11
12
13
"""
@param nums: an integer array
@return: nothing
"""
def moveZeroes(self, nums):
left, right = 0, 0
while right < len(nums):
if nums[right] != 0:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right += 1Remove Duplicate Numbers in Array
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
"""
@param nums: an array of integers
@return: the number of unique integers
"""
def deduplication(self, nums):
'''
O(nlog(n)) time complexity, O(1) space complexity
'''
if nums == []:
return 0
nums.sort()
start, end = 0, 1
while end < len(nums):
if nums[start] != nums[end]:
nums[start + 1] = nums[end]
start += 1
end += 1
return start+1
'''
O(n) time complexity, O(n) space complexity
'''
sub_list = list(set(nums))
for i in range(0, len(sub_list)):
nums[i] = sub_list[i]
return len(sub_list)Two Sum II - Input array is sorted
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
"""
@param nums: an array of Integer
@param target: target = nums[index1] + nums[index2]
@return: [index1 + 1, index2 + 1] (index1 < index2)
"""
def twoSum(self, nums, target):
left, right = 0, len(nums) -1
while left < right:
if nums[left] + nums[right] < target:
left += 1
elif nums[left] + nums[right] > target:
right -= 1
else:
return [left + 1, right + 1]
return [-1, -1]Sort colors II
Given an array of n objects with k different colors (numbered from 1 to k), sort them so that objects of the same color are adjacent, with the colors in the order 1, 2, … k.Could done with quick sort but not very efficient
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
"""
@param colors: A list of integer
@param k: An integer
@return: nothing
"""
def sortColors2(self, colors, k):
self.sort(colors, 1, k, 0, len(colors) - 1)
def sort(self, colors, color_from, color_to, index_from, index_to):
if color_from == color_to or index_from == index_to:
return
color = (color_from + color_to) // 2
left, right = index_from, index_to
while left <= right:
while left <= right and colors[left] <= color:
left += 1
while left <= right and colors[right] > color:
right -= 1
if left <= right:
colors[left], colors[right] = colors[right], colors[left]
left += 1
right -= 1
self.sort(colors, color_from, color, index_from, right)
self.sort(colors, color + 1, color_to, left, index_to)Three sum
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero
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
30
31
32
33
34
35
36
37
38
39
40
41
42
"""
@param numbers: Give an array numbers of n integer
@return: Find all unique triplets in the array which gives the sum of zero.
"""
def threeSum(self, numbers):
num_dict = {}
for i in numbers:
if i not in num_dict:
num_dict[i] = 0
num_dict[i] += 1
results = []
for i in num_dict:
target = i * -1
for j in num_dict:
k = target - j
if k in num_dict:
result = [i,j,k]
result.sort()
if i != j and j != k and i != k:
if result not in results:
results.append(result)
else:
if i == j and j == k:
if num_dict[i] > 2:
if result not in results:
results.append(result)
else:
if j == k:
if num_dict[j] > 1:
if result not in results:
results.append(result)
if i == k:
if num_dict[k] > 1:
if result not in results:
results.append(result)
if i == j:
if num_dict[j] > 1:
if result not in results:
results.append(result)
return list(results)Partition Array
Given an array nums of integers and an int k, partition the array (i.e move the elements in “nums”) such that:All elements < k are moved to the left All elements >= k are moved to the right Return the partitioning index, i.e the first index i nums[i] >= k.
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
"""
@param nums: The integer array you should partition
@param k: An integer
@return: The index after partition
"""
def partitionArray(self, nums, k):
lp, rp = 0, len(nums) - 1
while lp <= rp:
while lp <= rp and nums[lp] < k:
lp += 1
while lp <= rp and nums[rp] >= k:
rp -= 1
if lp <= rp:
nums[lp], nums[rp] = nums[rp], nums[lp]
lp += 1
rp -= 1
return lpTwo Sum - Unique pairs
Given an array of integers, find how many unique pairs in the array such that their sum is equal to a specific target number. Please return the number of pairs.
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
"""
@param nums: an array of integer
@param target: An integer
@return: An integer
"""
def twoSum6(self, nums, target):
if len(nums) < 2:
return 0
nums.sort()
left, right = 0, len(nums) - 1
result = 0
while left < right:
if nums[left] + nums[right] == target:
result, left, right = result + 1, left + 1, right - 1
while left < right and nums[right] == nums[right + 1]:
right -= 1
while left < right and nums[left] == nums[left - 1]:
left += 1
elif nums[left] + nums[right] < target:
left += 1
else:
right -= 1
return resultTwo Sum - Less than or equal to target
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
"""
@param nums: an array of integer
@param target: an integer
@return: an integer
"""
def twoSum5(self, nums, target):
nums.sort()
left, right = 0, len(nums) - 1
result = 0
while left < right:
if nums[left] + nums[right] > target:
right -= 1
else:
result += (right - left)
left += 1
return resultTwo Sum - Closest to target
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
"""
@param nums: an integer array
@param target: An integer
@return: the difference between the sum and the target
"""
def twoSumClosest(self, nums, target):
nums.sort()
left, right = 0, len(nums)-1
diff = 9999999999999
while left < right:
if nums[left] + nums[right] < target:
diff = min(diff, target - (nums[left] + nums[right]))
left += 1
elif nums[left] + nums[right] > target:
diff = min(diff, (nums[left] + nums[right]) - target)
right -= 1
else:
return 0
return diffFor case involve 3 pointer, for loop first and then use two pointer
3Sum Closest
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers.
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
"""
@param numbers: Give an array numbers of n integer
@param target: An integer
@return: return the sum of the three integers, the sum closest target.
"""
def threeSumClosest(self, numbers, target):
numbers.sort()
ans = None
for i in range(len(numbers)):
left, right = i + 1, len(numbers) - 1
while left < right:
sum = numbers[left] + numbers[right] + numbers[i]
if ans is None or abs(sum - target) < abs(ans - target):
ans = sum
if sum <= target:
left += 1
else:
right -= 1
return ansTriangle Count
Given an array of integers, how many three numbers can be found in the array, so that we can build an triangle whose three edges length is the three numbers that we find?
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
"""
@param S: A list of integers
@return: An integer
"""
def triangleCount(self, S):
# write your code
S.sort()
ans = 0
for i in range(len(S)):
left, right = 0, i -1
while left < right:
if S[right] + S[left] > S[i]:
ans += right - left
right -= 1
else:
left += 1
return ansKth Smallest Numbers in Unsorted Array
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
30
31
32
"""
@param k: An integer
@param nums: An integer array
@return: kth smallest element
"""
def kthSmallest(self, k, A):
# write your code here
if not A or k < 1 or k > len(A):
return None
return self.partition(A, 0, len(A) - 1, k)
def partition(self, A, start, end, k):
if start == end:
return A[k-1]
left, right = start, end
mid = A[(left + right) // 2]
while left <= right:
while left <= right and A[left] < mid:
left += 1
while left <= right and A[right] > mid:
right -= 1
if left <= right:
A[left], A[right] = A[right], A[left]
left += 1
right -= 1
if k <= right:
return self.partition(A, start, right, k)
if k >= left:
return self.partition(A, left, end, k)
return A[k-1]
近期评论