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 两数之和

  题目描述

  i> 给定一个整数数组 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 []