leetcode第一题

Tom2Code

发布于 2023-08-31 14:12:17

1210

发布于 2023-08-31 14:12:17

文章被收录于专栏：Tom

两种思路

第一种：先遍历一遍数组，使用target减去数组中每一个元素得到一个差，然后再去遍历数组，看看数组中是否存在一个和这个差一样的数。如果存在，那么则代表查找成功。否则查找失败。

第一种思路的算法时间复杂度是O(N2)

直接上代码：

from typing import List
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                if nums[i] + nums[j] == target:
                    return [i, j]

        return []

    def buTom(self,nums:List[int],target:int)-> List[int]:
        #n=len(nums)
        for i in range(len(nums)):
            temp=target-nums[i]
            for m in range(len(nums)):
                if temp==nums[m]:
                    return [i,m]

        return []

b=[2,5,6]

tom=Solution()

print(tom.twoSum(b,7))
print(tom.buTom(b,7))

第一个函数是leetcode官方的代码，第二个Tom edition

运行结果：

第二种方法就是比较高级的，这是我通过leetcode官网学习到的，所以分享出来大家一起学习一下。第二种思路是通过哈希表

官方的代码是这样的：

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashtable = dict()
        for i, num in enumerate(nums):
            if target - num in hashtable:
                return [hashtable[target - num], i]
            hashtable[nums[i]] = i
        return []

作者：力扣官方题解
链接：https://leetcode.cn/problems/two-sum/solutions/434597/liang-shu-zhi-he-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

还有一个java版本，感觉java版本的更容易理解一些，但是也不容易想出来。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; ++i) {
            if (hashtable.containsKey(target - nums[i])) {
                return new int[]{hashtable.get(target - nums[i]), i};
            }
            hashtable.put(nums[i], i);
        }
        return new int[0];
    }
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/two-sum/solutions/434597/liang-shu-zhi-he-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2023-06-03，如有侵权请联系 cloudcommunity@tencent.com 删除

int