python编程练习1-数组

1.两数之和

class Solution(object):def twoSum(self, nums, target):""":type nums: List[int]:type target: int:rtype: List[int]"""for i in range(len(nums)):res=target-nums[i]if res in nums[i+1:]:return [i,nums[i+1:].index(res)+i+1]

2. 三数之和（排序+双指针）

    题目中要求找到所有「不重复」且和为 0 的三元组，这个「不重复」的要求使得我们无法简单地使用三重循环枚举所有的三元组。

        「不重复」的本质是什么？我们保持三重循环的大框架不变，只需要保证：

        第二重循环枚举到的元素不小于当前第一重循环枚举到的元素；

        第三重循环枚举到的元素不小于当前第二重循环枚举到的元素。

        也就是说，我们枚举的三元组 (a,b,c) 满足 a≤b≤c。我们可以将数组中的元素从小到大进行排序，随后使用普通的三重循环就可以满足上面的要求。

        同时，对于每一重循环而言，相邻两次枚举的元素不能相同，否则也会造成重复。举个例子，如果排完序的数组为

[0, 1, 2, 2, 2, 3]

        我们使用三重循环枚举到的第一个三元组为 (0,1,2)，如果第三重循环继续枚举下 一个元素，那么仍然是三元组 (0,1,2)，产生了重复。因此我们需要将第三重循环「跳到」下一个不相同的元素，即数组中的最后一个元素 3，枚举三元组 (0,1,3)

        这种方法的时间复杂度仍然为 O(N3)，毕竟我们还是没有跳出三重循环的大框架。然而它是很容易继续优化的，可以发现，如果我们固定了前两重循环枚举到的元素 a 和 b，那么只有唯一的 c 满足 a+b+c=0。当第二重循环往后枚举一个元素 b ′时，由于 b ′>b，那么满足 a+b ′+c ′=0 的 c′，一定有 c′<c，即 c ′在数组中一定出现在 c 的左侧。也就是说，我们可以从小到大枚举 b，同时从大到小枚举 c，即第二重循环和第三重循环实际上是并列的关系。

  有了这样的发现，我们就可以保持第二重循环不变，而将第三重循环变成一个从数组最右端开始向左移动的指针。

  这个方法就是我们常说的「双指针」，当我们需要枚举数组中的两个元素时，如果我们发现随着第一个元素的递增，第二个元素是递减的，那么就可以使用双指针的方法，将枚举的时间复杂度从 O(N2) 减少至 O(N)。为什么是 O(N) 呢？这是因为在枚举的过程每一步中，「左指针」会向右移动一个位置（也就是题目中的 b），而「右指针」会向左移动若干个位置，这个与数组的元素有关，但我们知道它一共会移动的位置数为 O(N)，均摊下来，每次也向左移动一个位置，因此时间复杂度为 O(N)。

注意到我们的伪代码中还有第一重循环，时间复杂度为 O(N)，因此枚举的总时间复杂度为 O(N2)。由于排序的时间复杂度为 O(NlogN)，在渐进意义下小于前者，因此算法的总时间复杂度为 O(N2)。

   class Solution:def threeSum(self, nums: List[int]) -> List[List[int]]:  #-> List[List[int]]：这是函数的返回类型提示，表示这个函数应该返回一个由整数列表组成的列表。也就是说，返回值是一个二维数组，其中每个元素本身也是一个整数列表。n = len(nums)nums.sort()ans = list()# 枚举 afor first in range(n):# 需要和上一次枚举的数不相同if first > 0 and nums[first] == nums[first - 1]:continue# c 对应的指针初始指向数组的最右端third = n - 1target = -nums[first]# 枚举 bfor second in range(first + 1, n):# 需要和上一次枚举的数不相同if second > first + 1 and nums[second] == nums[second - 1]:continue# 需要保证 b 的指针在 c 的指针的左侧while second < third and nums[second] + nums[third] > target:third -= 1# 如果指针重合，随着 b 后续的增加# 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环if second == third:breakif nums[second] + nums[third] == target:ans.append([nums[first], nums[second], nums[third]])return ans

3.最接近的三数之和「排序+双指针」

解法同题2，采用排序和双指针的方法。

这里的「最接近」即为差值的绝对值最小。我们可以考虑直接使用三重循环枚举三元组，找出与目标值最接近的作为答案，时间复杂度为 O(N3 )。然而本题的 N 最大为 1000，会超出时间限制。

如何进行优化？我们首先考虑枚举第一个元素 a，对于剩下的两个元素 b 和 c，我们希望它们的和最接近 target−a。对于 b 和 c，如果它们在原数组中枚举的范围（既包括下标的范围，也包括元素值的范围）没有任何规律可言，那么我们还是只能使用两重循环来枚举所有的可能情况。因此，我们可以考虑对整个数组进行升序排序，这样一来：

假设数组的长度为 n，我们先枚举 a，它在数组中的位置为 i；

为了防止重复枚举，我们在位置 [i+1,n) 的范围内枚举 b 和 c。

当我们知道了 b 和 c 可以枚举的下标范围，并且知道这一范围对应的数组元素是有序（升序）的，那么我们是否可以对枚举的过程进行优化呢？

答案是可以的。借助双指针，我们就可以对枚举的过程进行优化。我们用 pb和 pc， 分别表示指向 b 和 c 的指针，初始时，pb指向位置 i+1，即左边界；pc指向位置 n−1，即右边界。在每一步枚举的过程中，我们用 a+b+c 来更新答案，并且：

如果 a+b+c≥target，那么就将 pc，向左移动一个位置；

如果 a+b+c<target，那么就将 pb，向右移动一个位置。

小优化

本题也有一些可以减少运行时间（但不会减少时间复杂度）的小优化。当我们枚举到恰好等于 target 的 a+b+c 时，可以直接返回 target 作为答案，因为不会有再比这个更接近的值了。

另一个优化与 15. 三数之和的题解 中提到的类似。当我们枚举 a,b,c 中任意元素并移动指针时，可以直接将其移动到下一个与这次枚举到的不相同的元素，减少枚举的次数。

class Solution:def threeSumClosest(self, nums, target):nums.sort()n = len(nums)best = 10**7   #初始化best的值，定义为一个很大的值# 根据差值的绝对值来更新答案def update(cur):nonlocal best #声明best为非局部变量，可以更新外部函数best的值if abs(cur - target) < abs(best - target):best = cur# 枚举 afor i in range(n):# 保证和上一次枚举的元素不相等if i > 0 and nums[i] == nums[i - 1]:continue# 使用双指针枚举 b 和 cj, k = i + 1, n - 1while j < k:s = nums[i] + nums[j] + nums[k]# 如果和为 target 直接返回答案if s == target:return targetupdate(s)if s > target:# 如果和大于 target，移动 c 对应的指针k0 = k - 1# 移动到下一个不相等的元素while j < k0 and nums[k0] == nums[k]:k0 -= 1k = k0else:# 如果和小于 target，移动 b 对应的指针j0 = j + 1# 移动到下一个不相等的元素while j0 < k and nums[j0] == nums[j]:j0 += 1j = j0return best

4.盛最多水的容器（双指针）

分析：

[1, 8, 6, 2, 5, 4, 8, 3, 7]

在初始时，左右指针分别指向数组的左右两端，它们可以容纳的水量为 min(1,7)∗8=8。

此时我们需要移动一个指针。移动哪一个呢？直觉告诉我们，应该移动对应数字较小的那个指针（即此时的左指针）。这是因为，由于容纳的水量是由

两个指针指向的数字中较小值∗指针之间的距离  决定的。如果我们移动数字较大的那个指针，那么前者「两个指针指向的数字中较小值」不会增加，后者「指针之间的距离」会减小，那么这个乘积会减小。因此，我们移动数字较大的那个指针是不合理的。因此，我们移动 数字较小的那个指针。

有读者可能会产生疑问：我们可不可以同时移动两个指针？ 先别急，我们先假设 总是移动数字较小的那个指针 的思路是正确的，在走完流程之后，我们再去进行证明。

所以，我们将左指针向右移动：

[1, 8, 6, 2, 5, 4, 8, 3, 7]
    ^                    ^
此时可以容纳的水量为 min(8,7)∗7=49。由于右指针对应的数字较小，我们移动右指针：

[1, 8, 6, 2, 5, 4, 8, 3, 7]
    ^                 ^
此时可以容纳的水量为 min(8,3)∗6=18。由于右指针对应的数字较小，我们移动右指针：

[1, 8, 6, 2, 5, 4, 8, 3, 7]
    ^              ^
此时可以容纳的水量为 min(8,8)∗5=40。两指针对应的数字相同，我们可以任意移动一个，例如左指针：

[1, 8, 6, 2, 5, 4, 8, 3, 7]
       ^           ^
此时可以容纳的水量为 min(6,8)∗4=24。由于左指针对应的数字较小，我们移动左指针，并且可以发现，在这之后左指针对应的数字总是较小，因此我们会一直移动左指针，直到两个指针重合。在这期间，对应的可以容纳的水量为：min(2,8)∗3=6，min(5,8)∗2=10，min(4,8)∗1=4。

在我们移动指针的过程中，计算到的最多可以容纳的数量为 49，即为最终的答案。

class Solution:def maxArea(self, height: List[int]) -> int:l,r=0,len(height)-1ans=0while l<r:area=min(height[l],height[r])*(r-l)ans=max(ans,area)if height[l]<=height[r]:l+=1 #左指针右移else:r-=1 #右指针左移return ans