题目
leetcode-1.两数之和
我的
解题思路：
排序后，折半查找时间复杂度： O(nlogn) (其实取决于排序算法的时间复杂度，这里默认快排，最小的时间复杂度)空间复杂度：O(n)
解题代码：
class Solution:
def __init__(self):
self.resl = 0
self.resr = 0
def twoSum(self, nums: List[int], target: int) -> List[int]:
numsTemp = sorted(nums) # 快排 时间复杂度O(nlogn)
print(nums)
self.twoSumLoop(numsTemp,target,0,len(nums)-1) # 递归twoSumLoop 时间复杂度O(n)
resl = nums.index(numsTemp[self.resl]) # 求指定元素的第一个下标 时间复杂度O(n)
resr = nums.index(numsTemp[self.resr]) # 求指定元素的第一个下标 时间复杂度O(n)
if resl == resr:
for index in range(0,len(nums)): # 求指定元素的第二个下标 时间复杂度O(n)
if nums[index] == nums[resl] and index != resl:
resr = index
break
return [resl,resr] # 综上 时间复杂度O(nlogn)
def twoSumLoop(self, nums: List[int], target: int, l: int, r: int) -> List[int]: # 递归函数
if (nums[l]+nums[r]) == target:
print('test0')
print('[',l,',',r,']')
self.resl = l
self.resr = r
return
elif nums[l]+nums[r]>target:
# max+min > t
# 缩小max
print('test1')
r -= 1
print(r)
self.twoSumLoop(nums,target,l,r)
elif nums[l]+nums[r] # max+min < t # 放大min print('test2') l += 1 self.twoSumLoop(nums,target,l,r) 更好的 解题思路： 哈希表映射时间复杂度：O(n)（只需要遍历一次数组）空间复杂度：O(n) 解题代码： def twoSum(nums, target): hashmap={} for ind,num in enumerate(nums): # 建立Hash表 """ enumerate() 函数用于将一个可遍历的数据对象 (如列表、元组或字符串)组合为一个索引序列， 同时列出数据和数据下标，一般用在 for 循环当中。""" hashmap[num] = ind for i,num in enumerate(nums): j = hashmap.get(target - num) if j is not None and i!=j: return [i,j] """ 作者：lao-la-rou-yue-jiao-yue-xiang 链接：https://leetcode-cn.com/problems/two-sum/solution/xiao-bai-pythonji-chong-jie-fa-by-lao-la-rou-yue-j/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 """ Python解法不能直接用 dict，因为dict会去重Hash可以解决重复 key的原因 Hash为什么不怕重复。看评论里有很多人提出这个问题，说hash冲突。 我在这里解答一下这个问题。 1.每次写入时，判断条件不是当前的key本身存不存在，而是key和 tag 之间的差值存不存在，这一点很重要。 2.题目命题说明了一点，假定只有一个解。也就是说重复元素再多都无所谓。 case 1：如果有3个或者以上的重复元素，代表这个重复元素不可能是解，所以写入map的时候直接覆盖也无所谓； case2：如果只有两个重复元素，同样的道理，假如这个重复元素是解，那么必定是两个重复元素的和等于tag。这种情况下，当遇到第二个重复元素时，不会写入map，这个时候直接已经取到解了。 所以这种方式，不用考虑hash冲突的问题。 //语言java class Solution { public int[] twoSum(int[] nums, int target) { Map for(int i = 0; i< nums.length; i++) { if(map.containsKey(target - nums[i])) { return new int[] {map.get(target-nums[i]),i}; } map.put(nums[i], i); } throw new IllegalArgumentException("No two sum solution"); } } /* 作者：guanpengchn 链接：https://leetcode-cn.com/problems/two-sum/solution/jie-suan-fa-1-liang-shu-zhi-he-by-guanpengchn/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 */
发表评论