LeetCode11 盛最多水的容器
LeetCode11.png
算法流程：设置双指针i，j位于数组两端代表容器壁，每次让数字较小（高端较低）的一端向中间收缩一格，遍历一遍寻找最大的面积
证明：由于又两端构成的容器面积由较矮的一端以及两端之间的间距构成，即
因此如果从两端向内侧收缩，则只存在两种可能：
- 如果较长一端向内收缩，水槽的短板
只会变小或着不变
- 如果较短一端向内收缩，水槽的短板可能变大也可能变小
因而按照如上规则遍历，结束后就能找到使面积最大的组合的 减小到n。
Python 代码：
class Solution:
def maxArea( self, height: List[int] ) -> int:
i, j, area = 0, len(height)-1, 0
while i < j:
if height[i] < height[j]:
area = max(area, height[i]*(j-i))
i += 1
else:
area = max(area, height[j]*(j-i))
j -= 1
return area
复杂度分析：
时间复杂度：
空间复杂度：
LeetCode202 快乐数
LeetCode202.png
分析问题很容易得出只要循环计算给定整数的各位数字的平方和，直到出现1就满足条件，输出True。问题的关键是当给定数字不满足时，如何跳出循环，即寻找循环终止的条件。
-
一种方法是，寻找规律，小于10的数，只有1和7满足条件，所以可以一直计算到平方和小于10。然后判断是否等于1或7
class Solution: def isHappy(self, n: int) -> bool: def digitSum(n: int) -> int: res = 0 tmp = 0 while n > 0: tmp = n % 10 res += tmp * tmp n /= 10 return res res = n while res >= 10: n = sum res = digitSum(n) return res == 1 or res == 7 -
另一种思路是判断出计算的平方和出现循环就终止计算，然后判断是否出现结果为1。这里判断出现循环用的思路就是快慢指针的思想，设置快指针，每次计算两遍平方和，满指针每次计算一次平方和。当出现快慢指针计算结果相同时，就说明计算出现了无限循环，此时就终止计算进行判断：
class Solution: def isHappy(self, n: int) -> bool: def digitSum(n: int) -> int: res = 0 tmp = 0 while n > 0: tmp = n % 10 res += tmp * tmp n /= 10 return res fast = slow = n while True: fast = digitSum(fast) fast = digitSum(fast) slow = digitSum(slow) if fast == slow: break return slow == 1上面的程序中需要注意，while中的循环至少需要计算一次，但是python中不支持do while 循环结构，所以需要在死循环中设置break来跳出循环。
LeetCode15 三数之和
LeetCode15.png
分析问题：
题目要求在给定数组中找出和为0的三个数组合。最直接的就是采用暴力搜索，检索所有可能的三数组合，但是这种方法效率太低，时间复杂度为 。针对暴力检索的方式可以采用哈希表的方式像两数之和那样进行优化。但是根据三数之和的性质，如果我们采用双指针的方法，同样可以巧妙的将算法的复杂度降低。
分析三数之和为零的条件：
- 除去三个数都为0的情况，三个数中的最小值和最大值必然是符号相反的。
- 除去三个数都为0的情况，三个数中的最小值必然是负数。
- 如果我们固定三个数中的其中1个，那么问题就转化为找到两个数的组合，这两个数的和为第一个数的相反数。
- 继续分析，如果是在一个排序过的数组中寻找两个数，它们的和为目标值。这时我们就可以使用双指针的方法，根据两数和与目标数的大小关系，分别从两端逼近。
根据第1，2点，我们可以增加终止循环的条件。根据第3，4点我们可以设计出整个代码的框架。
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
l = len(nums)
nums.sort()
res = []
for i in range(l): #分析3:固定一个数，使问题变为两数之和问题
if nums[i] > 0:
break #分析2: 最小数大于0直接结束
left = i+1
right = l-1
while left < right and nums[right] >= 0: #分析1：最大值必然大于等于0
val = nums[i] + nums[left] + nums[right]
if val == 0: #分析4: 采用双指针从数组两边逼近结果
res.append([nums[i], nums[left], nums[right]])
left += 1
right -= 1
elif val < 0:
left += 1
elif val > 0:
right -= 1
return res
对结果的去重：
我们根据分析使用双指针法写出了如上的代码，但是实际测试时会发现我们忽略了结果中存在着重复的数字组合。因为题目要求结果中不能存在重复的数字组合，所以在判断过程中还需要将重复出现的组合去掉。这一点对于排序过的数组是容易的，由于数组排序过，重复的数字是连续的。因此只需要在遍历的过程中分别对三个数字去重，跳过重复数字即可。故而对如上代码做出修改如下：
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
l = len(nums)
nums.sort()
res = []
for i in range(l): #分析3:固定一个数，使问题变为两数之和问题
if nums[i] > 0:
break #分析2: 最小数大于0直接结束
if i > 0 and nums[i] == nums[i-1]:
continue #去重1: 对选定的第一个数去重
left = i+1
right = l-1
while left < right and nums[right] >= 0: #分析1：最大值必然大于等于0
val = nums[i] + nums[left] + nums[right]
if val == 0: #分析4: 采用双指针从数组两边逼近结果
res.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left+1]:
left += 1 #去重2: 对第二个数去重
while left < right and nums[right] == nums[right-1]:
right -= 1 #去重3: 对第三个数去重
left += 1
right -= 1
elif val < 0:
left += 1
elif val > 0:
right -= 1
return res
复杂度分析：
时间复杂度：一次排序加两趟遍历，时间复杂度为
空间复杂度：
LeetCode1013 将数组分成和相等的三个部分
LeetCode1013.png
- 首先分析数组能被分为和相等的三个部分的条件必然是整个数组的和能被3整除，因此通过这个条件可以直接判断是否可以直接返回false。
- 然后通过求出整个和的数组的三分之一，就能知道每一部分和的大小。直接通过暴力方法遍历累加到目标值即可求解，但是由于是分成三组，所以要求解两遍，如果采用双指针方法分别从两边遍历求和，只需要在一次遍历中完成。
class Solution:
def canThreePartsEqualSum(self, A: List[int]) -> bool:
s = sum(A)
if s % 3:
return False
target = s // 3
i, j = 0, len(A)-1
s1, s3 = A[i], A[j]
while i+1 < j:
if s1 != target:
i += 1
s1 += A[i]
if s3 != target:
j -= 1
s3 += A[j]
if s1 == target and s3 == target:
break
return i+1 < j
复杂度分析：
时间复杂度：
空间复杂度：O(1)
注意：
虽然使用双指针可以使代码看起来更简洁，但其实并没有使复杂度降低，所以双指针方法在这里实际的意义不大。
网友评论