1879. 两数之和 VII

1879. 两数之和 VII

中文English

给定一个已经 按绝对值升序排列 的数组,找到两个数使他们加起来的和等于特定数。

函数应该返回这两个数的下标,index1必须小于index2。注意返回的值是0-based。

你不能对该数组进行排序。

样例

输入: 
[0,-1,2,-3,4]
1
输出: [[1,2],[3,4]]
说明: nums[1] + nums[2] = -1 + 2 = 1, nums[3] + nums[4] = -3 + 4 = 1
你也可以返回 [[3,4],[1,2]],系统将自动帮你排序成 [[1,2],[3,4]]。但是[[2,1],[3,4]]是不合法的。

挑战

\mathcal{O}(n)O(n)的时间复杂度和\mathcal{O}(1)O(1)的额外空间复杂度

注意事项

  • 数据保证numsnums中的所有数的互不相同的。
  • numsnums数组长度\leq 100\,000≤100000
  • numsnums内的数\leq 10^9≤10​9​​
输入测试数据 (每行一个参数)如何理解测试数据?

 

class Solution:
    """
    @param nums: the input array
    @param target: the target number
    @return: return the target pair
    """
    def twoSumVII(self, nums, target):
        # write your code here
        l = len(nums)
        res = []
        
        for index1 in range(l):
            if target - nums[index1] in nums:
                index2 = nums.index(target - nums[index1])
                
                if index1 < index2:
                    add_res = [index1, index2]
                    if add_res not in res:
                        res.append(add_res)
                elif index2 < index1:
                    add_res = [index2, index1]
                    if add_res not in res:
                        res.append(add_res)

        return res
                    

注:lintcode未通过,时间复杂度问题,待优化

上一篇:双指针应用一:碰撞指针


下一篇:167. Two Sum II - Input array is sorted