群内编号：2
本期活动最后一次打卡，感谢DataWhale提供的学习机会！
博文内容学习自DataWhale开源文档：
LeetCode分类训练 Task 3 查找

---

1. 两数之和

暴力法$O(n^2)$
空间上还过得去，不过非常非常耗时。

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[j] == target - nums[i]:
                    return [i, j]

排序+指针对撞$(O(n)+O(nlogn)=O(n))$
因为问题本身不是有序的，因此需要对原来的数组进行一次排序，排序后就可以用$O(n)$的指针对撞进行解决。

但是问题是，返回的是数字的索引，如果只是对数组的值进行排序，那么数组原来表示的索引的信息就会丢失，所以在排序前要进行些处理。

错误代码示例–只使用dict来进行保存：

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        record = dict()
        for index in range(len(nums)):
            record[nums[index]] = index 
        nums.sort()
        l,r = 0,len(nums)-1
        while l < r:
            if nums[l] + nums[r] == target:
                return [record[nums[l]],record[nums[r]]]
            elif nums[l] + nums[r] < target:
                l += 1
            else:
                r -= 1

当遇到相同的元素的索引问题时，会出错。如：[3,3] 6。

这里学习文档上提供的方法使用了一个bool型变量sameFlag来记录是否有相同元素出现。个人认为这个是没必要的，文档上所给代码能够AC原因也不是加入了这个bool型变量，而是因为重新遍历了一次列表，遍历过程本身带有顺序，从而一前一后取出了两个值相等的元素的不同索引。代码如下（相比文档上的删去了sameFlag，仍然AC）：

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        nums_copy = nums.copy()
        nums.sort()
        l,r = 0,len(nums)-1
        while l < r:
            if nums[l] + nums[r] == target:
                break
            elif nums[l] + nums[r] < target:
                l += 1
            else:
                r -= 1
        res = []
        for i in range(len(nums)):
            if nums_copy[i] == nums[l]:
                res.append(i)
            elif nums_copy[i] == nums[r]:
                res.append(i)
        return res

再给出一个更加pythonic的实现：通过list(enumerate(nums))开始实现下标和值的绑定，在使用lambda表达式指定按照数值来排序就OK了。

class Solution:
    def twoSum(self, nums, target):
        nums = list(enumerate(nums))
        nums.sort(key = lambda x:x[1])
        i,j = 0, len(nums)-1
        while i < j:
            if nums[i][1] + nums[j][1] > target:
                j -= 1
            elif nums[i][1] + nums[j][1] < target:
                i += 1
            else:
        # 这个if语句就是交换一下顺序，使其按升序输出，不必要
                if nums[j][0] < nums[i][0]:
                    nums[j],nums[i] = nums[i],nums[j]
                return nums[i][0],nums[j][0]

15. 三数之和

这里给出几种容易出现的错误：
1）没有考虑重复元素导致错误
直接使用Two Sum问题中的查找表的解法，根据第一层遍历的i，将i之后的数组作为two sum问题进行解决。

class Solution:
    def threeSum(self, nums: [int]) -> [[int]]:
        res = []
        for i in range(len(nums)):
            num = 0 - nums[i]
            record = dict()
            for j in range(i + 1, len(nums)):
                complement = num - nums[j]
                # 已经在之前的字典中找到这个值
                if record.get(complement) is not None:
                    res_lis = [nums[i], nums[j], complement]
                    res.append(res_lis)
                record[nums[j]] = i
        return res

错误用例

输入：
[-1,0,1,2,-1,-4]
输出：
[[-1,1,0],[-1,-1,2],[0,-1,1]]
预期结果：
[[-1,-1,2],[-1,0,1]]

2）剔除重复写在res.append()之前，导致实际记录的标号不对，有一些值不能被取出（比如说l和r取相邻的相等值时的情况）

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        if not nums or len(nums) < 3:
            return []
        nums.sort()
        res=[]
        for i in range(len(nums) - 2):
            if nums[0] > 0:
                break
            if i > 0 and nums[i] == nums[i-1]:
                continue
            l = i + 1
            r = len(nums) - 1
            while l < r:
                summation = nums[i] + nums[l] + nums[r]
                while l < r and nums[l] == nums[l+1]:
                    l += 1
                while l < r and nums[r] == nums[r-1]:
                    r -= 1
                if summation == 0:
                    res.append([nums[i], nums[l], nums[r]])
                    l += 1
                    r -= 1
                elif summation > 0:
                    r -= 1
                else:
                    l += 1
        return res

错误用例

输入：
[-4,-2,1,-5,-4,-4,4,-2,0,4,0,-2,3,1,-5,0]
输出：
[[-5,1,4],[-4,0,4],[-4,1,3],[-2,-2,4]]
预期：
[[-5,1,4],[-4,0,4],[-4,1,3],[-2,-2,4],[-2,1,1],[0,0,0]]

3）为补救2）出现的问题，修改判断条件为l <= r，此时会导致l和r均取到本来只出现一次的值：
代码就是把2）中的代码第二个循环while l < r修改为while l <= r。

错误用例

输入：
[-1,0,1,2,-1,-4]
输出：
[[-4,2,2],[-1,-1,2],[-1,0,1]]
预期结果：
[[-1,-1,2],[-1,0,1]]

正确写法

class Solution:
    def threeSum(self, nums):
        if not nums or len(nums) < 3:
            return []
        nums.sort()
        res = []
        for i in range(len(nums) - 2):
            if nums[i] > 0:
                break
            if i > 0 and nums[i] == nums[i-1]:
                continue
            l = i + 1
            r = len(nums) - 1
            while l < r:
                summation = nums[i] + nums[l] + nums[r]
                if summation == 0:
                    res.append([nums[i], nums[l], nums[r]])
                    while l < r and nums[l] == nums[l + 1]:
                        l += 1
                    while l < r and nums[r] == nums[r - 1]:
                        r -= 1
                    l += 1
                    r -= 1
                elif summation > 0:
                    r -= 1
                else:
                    l += 1
        return res

18. 四数之和

此题与3Sum问题思路完全相同，增加一层循环嵌套即可，这里不再赘述。

16. 最接近的三数之和

解决这个问题只需要在3Sum问题的代码上修修补补就好了，主要的改动就是加入了求差的过程。
伪代码

# 先排序
nums.sort()
# 随机选择一个和作为结果值
res = nums[0] + nums[1] + nums[2]
# 记录这个差值
diff = abs(nums[0]+nums[1]+nums[2]-target)
# 第一遍遍历
for i in range(len(nums)):
    # 标记好剩余元素的l和r
    l,r = i+1, len(nums-1)
    while l < r:
        if 后续的值等于target:
            return 三个数值得和
        else:
            if 差值小于diff:
                更新diff值
                更新res值
            if 和小于target:
                将l移动
            else:(开始已经排除了等于得情况，要判断和大于target)
                将r移动

我的代码

class Solution:
    def threeSumClosest(self, nums, target):
        if not nums or len(nums) < 3:
            return []
        nums.sort()
        closest = sum(nums[:3])
        mindelta = abs(sum(nums[:3]) - target)
        for i in range(len(nums) - 2):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            l = i + 1
            r = len(nums) - 1
            while l < r:
            # 这个循环可以不要
            # 这里主要起加速作用，相同的值其和肯定已被考虑过了
                summation = nums[i] + nums[l] + nums[r]
                delta = abs(summation - target)
                if delta == 0:
                    return summation
                    while l < r and nums[l] == nums[l + 1]:
                        l += 1
                    while l < r and nums[r] == nums[r - 1]:
                        r -= 1
                    l += 1
                    r -= 1
                else:
                    if delta < mindelta:
                        mindelta = delta
                        closest = summation
                    elif summation > target:
                        r -= 1
                    else:
                        l += 1
        return closest

49. 字母异位词分组

一开始我的想法是使用242题的方法，遍历整个词表，求出每个词的组成字典。用这个字典去匹配其他词，然后再把已经匹配好的词加入visited列表中。理论上讲应该可以解出，但是遇超时了，以后再考虑一下优化问题，这里也贴出代码：

class Solution:
    def groupAnagrams(self, strs):
        results = []
        visited = []
        from collections import Counter
        for i in range(len(strs)):
            if strs[i] not in visited:
                tmp = [strs[i]]
                dic1 = Counter(strs[i])
                visited.append(strs[i])
            else:
                continue
            for j in range(i+1, len(strs)):
                dic2 = Counter(strs[j])
                if dic2 == dic1:
                    tmp.append(strs[j])
                    visited.append(strs[j])
            results.append(tmp)
        return results

再给出一个来自文档上给出的比较Pythonic的解法，这个解法逃脱除了使用list的桎梏。首先消解str的序关系，然后使用字典存储满足这个字符信息的str，从而简单地解决了问题，虽然效率一般（不过已经比我自己写的快多了），但是代码简洁。

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        from collections import defaultdict
        strs_dict = defaultdict(list)
        for str in strs:
            key = ''.join(sorted(list(str)))
            strs_dict[key] += str.split(',')
        return [v for v in strs_dict.values()]

219. 存在重复元素 II

暴力法（超时）

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                if nums[i] == nums[j] and abs(i-j) <= k:
                    return True
        else:
            return False

文档上给出的使用滑窗方法的解法，这个解法有一点NLP中BOW模型的感觉，滑窗中的词没有关注顺序，只是形成了词袋。超出滑窗长度时删去最远端的值。代码如下：

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        record = set()
        for i in range(len(nums)):
            if nums[i] in record:
                return True
            record.add(nums[i])
            if len(record) == k+1:
                record.remove(nums[i-k])
        return False

时间复杂度和空间复杂度均为$O(n)$。虽然AC，但是结果并没有太优越，难道有时间复杂度和空间复杂度均为$O(1)$的算法吗？之后再看看题解。
注意一下倒数第二行和倒数第三行，nums[i-k]会不会出现索引错误呢？答案是不会的，因为当len(record) == k+1时，i的大小一定达到（或超过）了k，因此不会出现索引错误。

220. 存在重复元素 III

暴力解法（居然能快过88%的玩家！）

class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
        if t == 0 and len(nums) == len(set(nums)):
            return False
        for i in range(len(nums)):
            for j in range(1,k+1):
                if i+j >= len(nums): break
                if abs(nums[i+j]-nums[i]) <= t: return True
        return False

修正219题的做法：

class Solution:
    def containsNearbyAlmostDuplicate(self, nums, k, t) -> bool:
        record = set()
        for i in range(len(nums)):
            if len(record) != 0:
                rec = list(record)
                find_index = self.lower_bound(rec,nums[i]-t)
                if find_index != -1 and rec[find_index] <= nums[i] + t:
                    return True
            record.add(nums[i])
            if len(record) == k + 1:
                record.remove(nums[i - k])
        return False
    def lower_bound(self, nums, target):
        low, high = 0, len(nums)-1
        while low<high:
            mid = int((low+high)/2)
            if nums[mid] < target:
                low = mid+1
            else:
                high = mid
        return low if nums[low] >= target else -1

上面的步骤存在着大量set和list的转换，导致实际运行速度非常慢。

447. 回旋镖的数量

暴力法复杂度$O(n^3)$。

为了减少时间复杂度，可以使用字典记录每种举例有多少点对（pairs），然后求这个点对的取出2个的组合数即可。

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        times = 0
        from collections import Counter
        for i in points:
            record = Counter()
            for j in points:
                if j != i:
                    record[self.dis_square(i, j)] += 1
            for v in record.values():
                times += v*(v-1)
        return times
        
    def dis_square(self, x: List[int], y: List[int]) -> float:
        return (x[0]-y[0])**2 + (x[1]-y[1])**2

454. 四数相加 II

对于查找表问题而言，很多时候到底要查找什么，是解决的关键。
1）如果我们把D当作查找表，可以使用三层循环遍历A, B, C。之后看是否再D（的相反数）中存在，存在的次数就是结果。这个算法的时间复杂度是$O(n^3)$。
2）进一步扩展这个思路，可以2-2分。首先对于C和D的数组，可以通过dict来记录其中和的个数，之后遍历结果在A与B的和中进行查找，找到的次数就是结果。
这里给出2）的代码：

class Solution:
    def fourSumCount(self, A: List[int], B: List[int], C: List[int], D: List[int]) -> int:
        from collections import Counter
        record = Counter()
        for i in range(len(A)):
            for j in range(len(B)):
                record[A[i]+B[j]] += 1
        res = 0
        for i in range(len(C)):
            for j in range(len(D)):
                find_num = 0 - C[i] - D[j]
                if record.get(find_num) != None:
                    res += record[find_num]
        return res   

Pythonic优化如下：

class Solution:
    def fourSumCount(self, A: List[int], B: List[int], C: List[int], D: List[int]) -> int:
        record = collections.Counter(a + b for a in A for b in B)
        return sum(record.get(- c - d, 0) for c in C for d in D)

---

查找还是很有难度的，这一次由于时间有限学得不深入不透彻，今后还要在实践中慢慢领会。

再次感谢Datawhale提供学习机会！完结撒花 ^ _ ^