Algorithem_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#
Direct traversal with double for loop, but 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 code is not considered an algorithm, so it needs to be optimized. Since the array is sorted, the index=0 is the smallest and the index=count-1 is the largest. Using the Two Pointer solution, two variables should be defined to start from the beginning and end together. If head+tail>target, the tail becomes smaller and moves forward, if head+tail<target, the head becomes larger and moves backward, if head+tail is equal to the result, return
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. Then traverse the array, if the difference between target-num is found in the dictionary, return [dic[target-num] + 1, index], if it is not in the dictionary, store {num: index} in the dictionary. Since the array is sorted and traversed from small to large, when the result is found, the index corresponding to the value in the ordered dictionary is smaller, so it is the first one.
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 method. The logic is to traverse the array, each time getting the difference between target and the current number, and what needs to be done is to find if there is this difference in the elements after the array; if so, return the corresponding index, if not, continue the next traversal.
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 find 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 []
}
}