20211208 | Leetcode每日算法

咬定青山不放松，立根原在破岩中。
千磨万击还坚劲，任尔东西南北风。

0x001、两数之和

地址：https://leetcode-cn.com/problems/two-sum/

方法一、暴力循环

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

方法二、哈希表

class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:item = {}for i in range(len(nums)):if target-nums[i] in item:return [item[target-nums[i]],i]else:item[nums[i]] = ireturn []

0x002、盛最多水的容器

地址：https://leetcode-cn.com/problems/container-with-most-water/

木桶能装多少水取决于最短的木板。

方法一、双指针

左右指针，每次移动比较矮的一侧。

class Solution:def maxArea(self, height: List[int]) -> int:left,right = 0,len(height)-1max_area = 0while left<right:area = (right-left)*(min(height[right],height[left]))max_area = max(max_area,area)if height[left]>=height[right]:right-=1else:left+=1return max_area

0x003、三数之和

地址：https://leetcode-cn.com/problems/3sum/

方法一、排序+双指针

• 长度小于3返回空列表
• 排序
  • 取锚点元素，如果锚点元素大于0，代表后面没有三数和为零的元素，直接break，毕竟排过序
  • 取锚点元素后一个为左指针left，最后一个为右指针right
  • 循环 left<right
    • 三数和大于零，右边距向左移动一位
    • 三数和小于零，左边距向右移动一位
    • 三数和等于零，添加到result
      • 判断左右边距是否重合，left是否等于left+1
        • left+=1
      • 判断左右边距是否重合，right是否等于right-1
        • right-=1
      • 收缩左右边距

class Solution:def threeSum(self, nums: List[int]) -> List[List[int]]:lenght = len(nums)result = list()if lenght<3:return resultnums.sort()for i in range(lenght):if nums[i]>0:breakif i>0 and nums[i]==nums[i-1]:continueleft,right = i+1,lenght-1while left<right:flag = nums[i] + nums[left] + nums[right]if flag>0:right-=1elif flag<0:left+=1else:result.append([nums[i],nums[left],nums[right]])while left<right and nums[left]==nums[left+1]:left+=1while left<right and nums[right]==nums[right-1]:right-=1right-=1left+=1return result

console.log("公众号:虫术")
Blog:http://404nofoundx.top/