算法练习-leetcode-1.两数之和

题目

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]<target:
            # 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<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");
    }
}

/* 	
	作者：guanpengchn
	链接：https://leetcode-cn.com/problems/two-sum/solution/jie-suan-fa-1-liang-shu-zhi-he-by-guanpengchn/
	来源：力扣（LeetCode）
	著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/