0001. 两数之和

1, 题目

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2, 算法

1, 排序

第一步,数组转化为带下标的tuple对
第二步,对tuple对按照value排序
第三步,从两头向中间搜索,和大于目标值,则减小,小于目标值,则增大,相等,则记录下标

# scala实现
object Solution {
    def twoSum(nums: Array[Int], target: Int): Array[Int] = {
        val nums_index = nums.zipWithIndex
        val nums_sorted = nums_index.sortBy(_._1)
        var sum = 0
        var left = 0
        var right = nums_sorted.length - 1
        val result = Array(0, 0)
        var flag = true
        while (flag && left < right) {
            sum = nums_sorted(left)._1 + nums_sorted(right)._1
            if (sum == target) {
                flag = false
                result(0) = nums_sorted(left)._2
                result(1) = nums_sorted(right)._2
            } else if (sum < target) {
                left += 1
            } else {
                right -= 1
            }
        }
        result
    }
}

#python3 实现
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        nums_index = [(value, index) for index, value in enumerate(nums)]
        nums_sorted = sorted(nums_index, key=lambda x: x[0])
        left = 0
        right = len(nums_sorted) - 1
        result = [0, 0]
        while left < right:
            sum = nums_sorted[left][0] + nums_sorted[right][0]
            if sum == target:
                result = [nums_sorted[left][1], nums_sorted[right][1]]
                break
            elif sum < target:
                left += 1
            else:
                right -= 1
        return result

2, hash

第一步, 判断两个相等值和是target,是,则直接返回,否则,进行下面步骤
第二步, hash value-->index
第二步, 差 in hash

#scala 实现
object Solution {
    def twoSum(nums: Array[Int], target: Int): Array[Int] = {
        val result = scala.collection.mutable.ArrayBuffer[Int]()
        if (target % 2 == 0) {
            val count = nums.count(_ == target / 2)
            if (count == 2) {
                nums.zipWithIndex.foreach {
                    case (value, index) => {
                        if (value == target / 2) {
                            result.append(index)
                        }
                    }
                }
                return result.toArray
            }
        }
        val nums_map = nums.zipWithIndex.toMap
        val index = nums.indexWhere(value => (value != target - value) && nums_map.contains(target - value))
        result.append(index)
        result.append(nums_map(target - nums(index)))

        result.toArray
    }
}

#python 实现
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        result = []
        if target % 2 == 0 and nums.count(target // 2) == 2:
            for index, value in enumerate(nums):
                if value == target // 2:
                    result.append(index)
            return result

        nums_map = dict([(value, index) for index, value in enumerate(nums)])
        for index, value in enumerate(nums):
            if value != target - value and target - value in nums_map:
                result.append(index)
                result.append(nums_map[target - value])
        return result