题目
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)
print(nums)
self.twoSumLoop(numsTemp,target,0,len(nums)-1)
resl = nums.index(numsTemp[self.resl])
resr = nums.index(numsTemp[self.resr])
if resl == resr:
for index in range(0,len(nums)):
if nums[index] == nums[resl] and index != resl:
resr = index
break
return [resl,resr]
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:
print('test1')
r -= 1
print(r)
self.twoSumLoop(nums,target,l,r)
elif nums[l]+nums[r]<target:
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):
""" 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冲突的问题。
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
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");
}
}
|