[数据结构与算法]Python数据结构1——数组

217. 存在重复元素

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。

方法一：逐个将数组内容加入集合，如果已经有了，就证明有重复元素

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        numSet=set()
        for i in nums:
            if i in numSet:
                return True
            else:
                numSet.add(i)
        return False

方法二：将数组转换为集合，比较集合和数组的长度，如果长度不同，证明数组中有重复元素

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        return len(set(nums))!=len(nums)

53. 最大子数组和?

给你一个整数数组?nums?，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组?是数组中的一个连续部分。

动态规划法

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        tmp = nums[0]
        max_ = tmp
        n = len(nums)
        for i in range(1,n):
            # 当当前序列加上此时的元素的值大于tmp的值，说明最大序列和可能出现在后续序列中，记录此时的最大值
            if tmp + nums[i]>nums[i]:
                max_ = max(max_, tmp+nums[i])
                tmp = tmp + nums[i]
            else:
            #当tmp(当前和)小于下一个元素时，当前最长序列到此为止。以该元素为起点继续找最大子序列,
            # 并记录此时的最大值
                max_ = max(max_, tmp, tmp+nums[i], nums[i])
                tmp = nums[i]
        return max_

1. 两数之和

给定一个整数数组 nums?和一个整数目标值 target，请你在该数组中找出 和为目标值 target??的那?两个?整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

方法一：暴力枚举

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]

方法二：哈希表

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap={}
        for ind,num in enumerate(nums):
            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]