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≤109
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未通过,时间复杂度问题,待优化