【LeetCode刷题】数组

No.217 存在重复元素

题目描述

i> 给定一个整数数组，判断是否存在重复元素。如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。

示例 1:

输入: [1,2,3,1]
 输出: true

示例 2:

输入: [1,2,3,4]
 输出: false

解题思路

代码实现

# 217. 存在重复元素
 class Solution:
     def containsDuplicate(self, nums: List[int]) -> bool:
         # 排序
         nums.sort()
         # 遍历数组，查找相邻元素是否相等
         for i in range (len(nums)-1):
                 if nums[i]== nums[i+1]:
                     return True
         return False

错误代码

# 错误：out of list range
 class Solution:
     def containsDuplicate(self, nums: List[int]) -> bool:
         for i, num in enumerate(nums):
             while nums[i] != i:
                 m = nums[i]
                 if nums[m] == m:
                     return True
                 else:
                     nums[i] = nums[m]
                     nums[m] = m
         return False

No.53 最大子序和

题目描述

i> 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
 输出：6
 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

提示：

1 <= nums.length <= 3 * 104

-105 <= nums[i] <= 105

解题思路

代码实现

class Solution:
     def maxSubArray(self, nums: List[int]) -> int:
         for i in range(1, len(nums)):
             if nums[i-1]>0:
                 nums[i] = nums[i] + nums[i-1]
         return max(nums)

No.1 两数之和

题目描述

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

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

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

示例 1：

输入：nums = [2,7,11,15], target = 9
 输出：[0,1]
 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

解题思路

暴力法
哈希表

代码实现

暴力法

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 []

哈希表

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