两数之和及其变式：在列表中寻找和为某值的两个元素的下标（题目+原理+python代码实现）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了两数之和及其变式：在列表中寻找和为某值的两个元素的下标（题目+原理+python代码实现），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2866字，纯文字阅读大概需要5分钟。

内容图文

在列表中寻找和为某值的两个元素的下标

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        n = len(nums)
        for i in range(n):
            for j in range(i+1,n):
                if nums[i]+nums[j]==target:
                    return sorted([i, j])   # 这个办法太慢了。                   

如果是一个排好序的列表，可以用二分查找。
167. 两数之和 II - 输入有序数组
给定一个已按照 升序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。
函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
示例 1：
输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

示例 2：
输入：numbers = [2,3,4], target = 6
输出：[1,3]

示例 3：
输入：numbers = [-1,0], target = -1
输出：[1,2]

class Solution(object):
    # def binary_search(self, li, val):
    #     left = 0
    #     right = len(li) - 1
    def binary_search(self, li, left, right, val):
        while left <= right:
            mid = (left + right) // 2
            if li[mid] == val:
                return mid
            elif li[mid] > val:
                right = mid - 1
            else:
                left = mid + 1
        else:
            return None


    def twoSum(self, nums, target):
        """
        :type numbers: List[int]
        :type target: int
        :rtype: List[int]
        """
        # 二分查找，列表一定是有序的就可以使用。但是还是不要输出自己和自己，即有重复的元素。即[2,6,7,8]找14，不要输出7和7的下标，应该输出6和8的下标。
        for i in range(len(nums)):
            a = nums[i]
            b = target - a
            if b >= a:
                # j = self.binary_search(li[i+1:], b)   这个切片过程有一个O(n)的时间复杂度。
                j = self.binary_search(nums, i+1, len(nums)-1, b)   #把左右箭头直接传进去。
            else:
                j = self.binary_search(nums, 0, i-1, b)
            if j:
                break
        return sorted([i+1, j+1])

推广一下，如果是一个没有排好序的列表，可以用二分查找吗?
没有序，可以排一下序，但是下标会变。记录一下之前的下标就可以。

class Solution(object):
    def binary_search(self, li, left, right, val):
        while left <= right:
            mid = (left + right) // 2
            if li[mid][0] == val:   # 二维列表
                return mid
            elif li[mid][0] > val:
                right = mid - 1
            else:
                left = mid + 1
        else:
            return None


    def twoSum(self, nums, target):
        """
        :type numbers: List[int]
        :type target: int
        :rtype: List[int]
        """
        new_nums = [[num, i] for i,num in enumerate(nums)]   # 二维列表的每一行有两个数，第一个是数字，第二个是i（下标）。
        new_nums.sort( key = lambda x:x[0])   # 二维列表排序，指定key。按照数进行排序。x[0]是数，x[1]是下标。
        # 比如 new_nums[i][0]是数字， new_nums[i][0]是原来的下标。
        
        for i in range(len(new_nums)):
            a = new_nums[i][0]
            b = target - a
            if b >= a:
                # j = self.binary_search(li[i+1:], b)   这个切片过程有一个O(n)的时间复杂度。
                j = self.binary_search(new_nums, i+1, len(nums)-1, b)   #把左右箭头直接传进去。
            else:
                j = self.binary_search(new_nums, 0, i-1, b)
            if j:
                break
        # return sorted([i, j])  是新的下标，应该输出旧的下标。
        return sorted([new_nums[i][1], new_nums[j][1]])
        # 时间复杂度为nlogn.

内容总结

以上是互联网集市为您收集整理的两数之和及其变式：在列表中寻找和为某值的两个元素的下标（题目+原理+python代码实现）全部内容，希望文章能够帮你解决两数之和及其变式：在列表中寻找和为某值的两个元素的下标（题目+原理+python代码实现）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端