LeetCode Hot100刷题日志D1

1.两数之和

给定一个整数数组nums和一个整数目标值target，请你在该数组中找出和为目标值target的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。你可以按任意顺序返回答案。

先是看了灵神的思路，用到了相向双指针的夹逼思想。整体思路是左右指针分别指向数组首尾，向中间夹逼。和大了右指针左移，和小了左指针右移。但是此算法仅适用于已经有序的数组。提交题解的时候未发现题目已经有所改变，已经变为无序，于是第一次提交失败。

后面看题解发现有哈希的做法，看了一遍原理后，想留着后面系统学习哈希算法时再使用，于是将目标转为暴力破解。暴力破解用的是双循环，时间复杂度为O(n*n)。

15.三数之和

给你一个整数数组nums，判断是否存在三元组[nums[i], nums[j], nums[k]]满足i != j、i != k且j != k，同时还满足nums[i] + nums[j] + nums[k] == 0。请你返回所有和为0且不重复的三元组。注意：答案中不可以包含重复的三元组。

先是顺着前面“两数之和”相向双指针的夹逼思想，这道题的整体思路是外层套一个 for 循环来固定第一个数，然后在剩下的区间里用左右指针去寻找和为 0 的另外两个数。在写的时候架上了剪枝优化（后面的数加起来都大于 0 就直接 break，加上最大的数还小于 0 就直接 continue）。
但是漏掉了一个最致命的前提：双指针能正确移动依赖于数组是有序的，原题给的数组是无序的，导致第一版代码逻辑直接崩溃。加上nums.sort()排序后再次提交，发现输出结果里包含了大量重复的三元组。
排查后发现，自己在寻找完一个正确组合后，去重逻辑错用了if语句。if只能跳过两个挨着的重复数字，遇到连续多个重复数字（比如连续三个 1）就失效了。于是立刻把if改成了while循环。
换成while提交后，发现IndexError数组越界报错。最后发现，在内部while跳过重复项时，忘了加上j < k的安全边界保护，导致左指针一路狂奔不仅越过了右指针，还冲出了数组外。改正后AC。