线性表（二）：顺序表的经典例题

引言

前文介绍了顺序表的基本操作，本文主要来分析有关顺序表的经典编程题目。

顺序表例题

两数之和

问题来源：
力扣：1. 两数之和

问题简述：
题目给定了一个target，要求在这个整数数组中找出两个整数的和恰好等于target，并返回整数的下标。

问题分析：
最简单的实现方法是枚举法，利用双层循环查找哪两个整数恰好和为target，只要查找到就返回结果，但这样做会使得平均时间复杂度为O(N^2)，效率较低。
正确的做法为设置一个哈希表，利用哈希表预先存储数组中元素的值和索引，然后线性扫描整个数组，如果发现哈希表中存在target-nums[i]的键且值不等于i则停止扫描，返回结果。

代码：

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        Hashtable = {}
        for i,j in enumerate(nums):
            Hashtable[j] = i
        for k in range(len(nums)):
            s = Hashtable.get(target - nums[k]) 
            if s != k and s is not None:
                return [k, s]

删除排序数组中的重复项

问题来源：
力扣：26. 删除排序数组中的重复项

问题简述：
给定一个排序数组，要求使用O(1)空间原地将重复项删除，并返回删除重复项后数组的长度。

问题分析：
本题难点在于将空间复杂度限制在O(1)层次，因此哈希计数、线性扫描等方法在此处无法使用。
由于题目中告知不需要考虑新长度后数组中的元素，因此我们可以考虑采用双指针（滑动窗口），将要删除的元素覆盖，即可实现重复项删除操作。

代码

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if len(nums) <= 1:
            return len(nums)
        else:
            a, b = 0, 1
            while b < len(nums):
                while b < len(nums) and nums[b] == nums[a]:
                    b += 1
                if b < len(nums):
                    a += 1
                    nums[a] = nums[b]
            return a + 1

盛最多水的容器

问题来源：
力扣：11. 盛水最多的容器

问题简述：
给出了宽度（索引之差），以及高度（最小元素值），求出最大矩形面积。

问题分析：
我们可以设定头尾指针，实时记录最大的矩形面积，指针更新按照如下规则：

1. 头指针对应的值更小，则头指针后退一位；
2. 尾指针对应的值更小，则尾指针前进一位；
3. 头尾指针对应的值相同，则相向进一位。

代码

class Solution:
    def maxArea(self, height: List[int]) -> int:
        a, b = 0, len(height)-1
        res = 0
        while a < b:
            res = max(res, min(height[a], height[b])*(b-a))
            if height[b] > height[a]:
                a += 1
            elif height[b] < height[a]:
                b -= 1
            else:
                a += 1
                b -= 1
        return res

三数之和

问题来源：
力扣：15. 三数之和

问题简述：
在一个整数数组中找出三个元素，这三个元素的和为0，输出所有满足条件且不重复的组合。

问题分析：
相信很多人对这道题的第一反应就是三层循环直接找出三个数并判断其和是否等于0，但这样做的时间复杂度为O(N^3)。
如何优化呢？我们可以将数组排序，排序后会发现上一个方法中后两层循环可以通过双指针合并成一个循环：
外层循环可以得到a的值，第二层循环可以得到b的值，不难发现，在a已知的情况下，b和c的值呈线性关系，若b偏大c必定偏小，反之亦然，我们将c通过一个指针指向数组尾部，在第二层循环中可以判断，若a+b+c>0，那么c对应的指针可以向前移动，因为可能成立的c值一定在左侧，又因为数组是升序排列，b的值只会不断增大，因此c的值必定呈递减趋势。

代码

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        nums.sort()
        ans = list()
        # 枚举 a
        for first in range(n):
            # 需要和上一次枚举的数不相同
            if first > 0 and nums[first] == nums[first - 1]:
                continue
            # c 对应的指针初始指向数组的最右端
            third = n - 1
            target = -nums[first]
            # 枚举 b
            for 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:
                    break
                if nums[second] + nums[third] == target:
                    ans.append([nums[first], nums[second], nums[third]])
        return ans