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

概述在列表中寻找和为某值的两个元素的下标classSolution(object):deftwoSum(self,nums,target):""":typenums:List[int]:typetarget:int:rtype:List[int]"""n=len(nums)foriin 在列表中寻找和为某值的两个元素的下标

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代码实现）所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。