Algorithem_TwoPointers

原创

莫空9081

发布于 2022-04-15 13:33:14

1350

发布于 2022-04-15 13:33:14

文章被收录于专栏：iOS 备忘录

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 numbersindex1 and numbersindex2 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].

解法一

直接遍历，双重 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 的值在字典里，则返回[dictarget-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 []
    }   
}

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

ios