一些LeetCode中等题做法（一）

记录一些LeetCode中等题解法。

15. 3Sum

题目：给定一个整数数组，求在数组中取三个数相加和为0的所有非重复元组。

做法：遍历数组建立map，使得查找某个值是否在数组中的操作变为O(1)，双重循环遍历数对，计算0减去这两个数得到M， 在map中查找M，如果找到则得到一个三元组，在插入结果数组之前，排序后用map去重。这个方法比较明显但是相对较慢，可以找到一个更好的解法。首先对数组排序，依次遍历各个数，相当于在剩下的数中选取两个指定和的数，用两个指针指向头和尾，根据两个指针指向的数之和与目标和的大小关系，移动指针寻找和为指定值的两个数，如果找到了就记录一下，然后把头尾指针移到和当前值不等的数上，在头尾重合的时候终止。遍历完第一个数后，要跳过和第一个数相等的数，这样最后就没有重复的三元组。

16. 3Sum Closest

题目：给定一个整数数组和目标整数，求在数组中取三个数相加离目标整数最近的整数。

做法：对数组排序，遍历数组中的除了后两个数以外的数，在剩下的数中记录头尾指针，如果对应的三个数的和比已经记录的最接近目标值的数还要接近目标值，则更新已经记录的值，根据和与目标值的大小关系移动头尾指针，大于目标值则尾指针减一，小于目标值则头指针加一。

18. 4Sum

题目：给定一个整数数组和目标整数，求所有和为目标整数的非重复四元组。

做法：对数组排序，双重循环遍历数对，根据情况移动保证前两个数组成的元组不重复，如果加上剩下的数中最大的两个依然小于目标值，或者加上最小的两个都大于目标值则跳过，接着就按照正常的两数和用头尾指针移动并去重，最后得到的是不重复的四元组。

454. 4Sum II

题目：4个等长整数数组，在4个数组中各取一个数求和为0，求取法数量。

做法：用map记录前两个数组中数对的和，key为和，value为数量，遍历后两个数组中的数对c和d，在前面记录的map中寻找0-c-d，如果找到了就增加对应数量的取法。

39. Combination Sum I

题目：给定一个整数集合和目标整数，集合中的数可以多次使用，求所有和为目标整数的非重复元组。

做法：对数组排序，递归调用，参数包含原整数数组，当前已经使用的数构成的数组，与目标整数的差值，遍历数组的起始位置。如果与目标整数的差值为0，将当前数组加入结果数组，否则遍历原整数数组，如果当前数小于等于当前目标值，将当前数加入已用数组，递归调用，然后把当前数弹出。

40. Combination Sum II

题目：给定一个整数数组和目标整数，数组中的数只能使用一次，求所有和为目标整数的非重复元组。

做法：与前一道题的差别在于当前遍历的数不能和上一个数相同，并且递归时遍历数组的起始位置要递增1。

74. Search a 2D Matrix

题目：每行递增排序的二维数组，并且每一行的开头大于前一行的末尾，查找是否包含目标值。

做法：相当于一个排序数组的二分查找，需要对一维下标和二维下标转化。

240. Search a 2D Matrix II

题目：每行每列都是递增排序的二维数组，查找是否包含目标值。

做法：如果取中点，划分出来的两部分不能形成子结构。初始为整个矩形区域，需要每次选取剩余矩形的右上角，如果右上角小于目标值，则去掉第一行，如果右上角大于目标值，则去掉最右边的列，是一个O(M+N)的解法。

137. Single Number II

题目：线性时间，O(1)空间，求每一个元素只可能出现一次或三次的整数数组中出现一次的数。

做法：这里的线性时间需要用到整数32位的限制，遍历一次数组，计算最末位的1的和，该和模3的结果是只出现一次的数的最末位的值，然后一次遍历32位，然后拼起来就得到结果。

260. Single Number III

题目：线性时间，O(1)空间，给定整数数组中有两个数只出现一次，其他的数都是出现两次，求只出现一次的两个数。

做法：这里需要用到异或的一个特性，如果一个数组只有一个数出现一次，其他数都是两次，对数组依次异或，最后的结果就是只出现一次的那个数。所以对原数组依次异或，得到的结果是那两个只出现一次的数的异或值，需要找到这个异或值的某位为1的位，根据这个位是否为1将原数组分成两组，对这两组数依次异或得到的两个值就是结果。

220. Contains Duplicate III

题目：给定长度为N的数组，整数K和T，如果可以在数组中找到两个数，下标差小于等于K，值的差的绝对值小于等于T，返回true，否则返回false。

做法：对每个数，需要考察前后下标在K以内的数，但是如果要遍历一次数组，实际需要考察每个数的前K个数里是否有满足条件的数。使用一个大小为K的滑动窗口，在遍历初期窗口大小可以小于K，该窗口内的数需要排序，并且需要经常插入和删除，所以使用map，map默认是排序的。对遍历的当前值A，在map中查找第一个大于等于A-T的数，如果该数与A的差的绝对值值小于等于T，则查找成功，否则维护窗口，继续遍历。

396. Rotate Function

题目：给定长度为N的数组，它有N个旋转数组，用0~N-1对应乘以旋转数组，求最大值。

做法：遍历原数组，记录0~N-1与对应元素的和Sum，以及所有元素的和S，记录初始最大值为Sum，遍历N-1次，每次进行一些操作，修改当前Sum，求与当前最大值的最大值，具体执行的操作示例如下。

0*4 + 1*3 + 2*2 + 3*6 初始值Sum

-1*4 + 0*3 + 1*2 + 2*6 (-= S)

0*4 + 0*3 + 1*2 + 2*6 (+= Ai)

3*4 + 0*3 + 1*2 + 2*6 (+= Ai * (N-1))

一开始i是0，操作完后从1开始，每次对应0*X的位置。

421. Maximum XOR of Two Numbers in an Array

题目：O(N)求非负整数数组取两个数进行异或运算的最大值。

做法：似乎涉及32位整数位运算的这个32的常数不算logN。把每个数按照二进制建二叉前缀树，对数组中的每个数，依次遍历二进制表示的各个位，如果为1，在树中尝试寻找0，如果没有0，就找1，为0则相反，找31次可以得到和该数异或的最大值。

424. Logest Repeating Character Replacement

题目：给一串大写字母和一个数字K，可用任意大写字母替换原串中某字母K次，求替换后最长相同字母子串长。

做法：滑动窗口初始化begin=end=0，同时维护窗口中26个大写字母各有几个。每次遍历先获取一个新的字母，修改对应字母的数量，递增end为后续移动窗口做准备。end-begin是当前窗口大小，end-begin-MAX(26个字母数量)是使得窗口内所有字母相同需要的替换次数，当这个次数大于K时，递增begin，修改对应字母数量。

窗口的初始长度为0，保证不需要替换也可以满足所有字母相同，窗口长度增加时如果使窗口内不满足条件，对于新增的字母，结果子串是否包含它有两种情况，如果不包含，当前的窗口就是从字符串头到这里的最大满足条件的窗口（如果此前有一个大于此窗口P的满足条件的窗口Q，此窗口P的左边缘会大于窗口Q的左边缘，遍历时一定会有当前左边缘与窗口Q左边缘重合的时候，不论当前右边缘是多少，在逐渐递增时一定会获得窗口Q），如果包含，把窗口的头去掉，包含进这个字母，得到的新窗口不一定满足条件（例如ABABACB，K=2，执行到C的时候，会把第一个A去掉，剩下的BABAC不满足条件）， 接下来移动窗口是为了找到比现在的窗口大的满足条件的窗口，如果接下来再也找不到更大的窗口，就会输出之前得到的窗口大小，如果某个窗口扩充1格可以满足条件，窗口就会增大1。相当于优化了双重循环遍历所有begin和end，根据串内情况计算是否满足条件，每个begin不需要遍历所有的长度，以某个点开始，如果长度为20的串是满足条件的，则长度1-19的都满足条件，如果已经找到了长度为20的串，下一个begin+1就不需要考察end=begin+1了，直接看begin+20，写成双重循环加break计算量是差不多的。