title: Algorithm_TwoPointers
tags:
- Technology
- Algorithm
date: 2022-04-15 09:24#
Algorithm_TwoPointers#
Two Sum II - Input Array Is Sorted#
Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.
Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.
The tests are generated such that there is exactly one solution. You may not use the same element twice.
Your solution must use only constant extra space.
Example 1:
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].
Example 2:
Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].
Example 3:
Input: numbers = [-1,0], target = -1
Output: [1,2]
Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].
Solution 1#
Directly traverse the array using a double for loop, but with i != j.
The code is as follows:
class Solution {
func twoSum(_ numbers: [Int], _ target: Int) -> [Int] {
var indexList: [Int] = []
for i in 0..<numbers.count {
for j in (i+1)..<numbers.count {
if numbers[i] + numbers[j] == target {
indexList.append(i+1)
indexList.append(j+1)
break
}
}
if indexList.count > 0 {
break
}
}
return indexList
}
}
However, the above solution is not considered an algorithm, so it needs to be optimized. Since the array is sorted, the element at index=0 is the smallest and the element at index=count-1 is the largest. We can use the Two Pointer approach, which defines two variables starting from the beginning and end of the array. If the sum of the elements at the start and end is greater than the target, we move the end pointer backward. If the sum is less than the target, we move the start pointer forward. If the sum is equal to the target, we return the indices.
The code is as follows:
class Solution {
func twoSum(_ numbers: [Int], _ target: Int) -> [Int] {
var i = 0;
var j = numbers.count - 1;
while (i < j) {
let small = numbers[i]
let big = numbers[j]
if small + big == target {
break
}
else if small + big < target {
i += 1
}
else {
j -= 1
}
}
return [i+1, j+1]
}
}
Solution 2#
This solution uses the functionality of a dictionary. The key of the dictionary is the value of the array, and the value is the index of the array. We iterate through the array, and if we find the difference between the target and the current number in the dictionary, we return [dic[target-num] + 1, index]. If it is not in the dictionary, we store {num: index} in the dictionary. Since the array is sorted and we iterate from small to large, when we find the result, the index corresponding to the smaller value in the ordered dictionary is returned first.
The code is as follows:
class Solution {
func twoSum(_ numbers: [Int], _ target: Int) -> [Int] {
var dic: [Int: Int] = [:]
for index in 0..<numbers.count {
let num = numbers[index]
if dic.keys.contains(target-num) {
return [dic[target-num]! + 1, index+1]
}
else {
dic[num] = index
}
}
return []
}
}
Solution 3#
This solution uses the Binary Search approach. The logic is to iterate through the array and get the difference between the target and the current number. Then, we need to search for this difference in the elements after the current number in the array. If it is found, we return the corresponding index [i+1, middle+1]. If it is not found, we continue to the next iteration.
The code is as follows:
class Solution {
func twoSum(_ numbers: [Int], _ target: Int) -> [Int] {
for i in 0..<numbers.count {
let num = numbers[i]
let tmp = target - num
// Then use binarySearch to check if there is an element equal to tmp
var l = i + 1
var r = numbers.count - 1
var middle = 0
while (l <= r) {
middle = l + (r - l) / 2
if numbers[middle] == tmp {
return [i+1, middle+1]
}
else if numbers[middle] < tmp {
l += 1
}
else {
r -= 1
}
}
}
return []
}
}