Algorithem_TwoPointers

2022-04-15

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:

1
2
3

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:

1
2
3

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:

1
2
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].

解法一

直接遍历，双重 for 循环，但是 i != j

代码如下：


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
    }
}

但是上面的没有算法可言，故而，需要优化，由于数组是有序的，所以，index=0的地方是最小的，index=count-1的地方是最大的，使用TwoPointer 的解法，应该是定义两个变量，从头和尾一起开始，头+尾>target，尾变小往前移，头+尾<target，头变大往后移，头+尾等于结果，则返回

代码如下：


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]
    }
}

解法二

这种解法是借助字典的功能，字典的 key 是数组的值，value 是数组的 index，然后遍历数组，如果发现 target-num 的值在字典里，则返回[dic[target-num] + 1, index]，如果不在字典里，则存储{num: index}到字典中。由于是数组有序，从小到大遍历，所以最终找到结果时返回顺序字典中value 对应的 index 是小的，所以在第一个

代码如下：


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 []
    }
}

解法三

这种解法是使用BinarySearch 解法，逻辑是，遍历数组，每次遍历得到target和当前数字的差值，然后需要做的是，在数组之后的元素中查找有没有这个差值；有则返回对应的 index，没有则继续下一次遍历

代码如下：


class Solution {
    func twoSum(_ numbers: [Int], _ target: Int) -> [Int] {        
        for i in 0..<numbers.count {
            let num = numbers[i]
            let tmp = target - num
            // 然后使用 binarySearch 查找有没有等于 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 []
    }   
}