15. 3Sum --- Medium
16. 3Sum Closest --- Medium
560. Subarray Sum Equals K --- Medium
189. Rotate Array --- Medium
1. 三数之和等于0 （Leetcode 15）
Leetcode 15
思路：
暴力解法 - for循环3轮，找到结果集，去重。但这效率太低，需要更高效的方法。
很容易想到先排序，再处理。快排，o(n * log n)时间复杂度。
接下来遍历该数组，对于其中的每一个元素nums[i]，找到另外两个元素nums[j] + nums[k] == nums[i].
其中对于每一个元素nums[i], j 初始化为 i+1, k 初始化为 length -1.
根据nums[j] + nums[k] 与 nums[i] 的大小比较，决定 j 往后移动，或者 k 往前移动，找满足条件的结果。
另外，需要注意，结果的list是不能包含重复组合的。
那么在遍历过程中，有两个地方需要处理好，才能把重复组合去掉：第 1 点是，遍历nums，移到 i，如果nums[i] == nums[i - 1]，那么当前的 i 是不需要被处理的，直接continue就好；第 2 点是，对于每一个nums[i],在移动 相应的 j，k指针时，每当找到一个结果，需要判断 j 后面的元素，以及 k 前面的元素，是不是与当前 j，k指向的元素相等，如果相等，直接将 j 往后移动，将 k 往前移动。
2. 最接近指定值的三数之和 （Leetcode 16）
Leetcode 16
思路：
与上一道3Sum比较类似。先排序。
for循环遍历nums，对于每一个nums[i], 用两个指针 j, k 遍历后面的元素，初始化 j = i +1, k = length - 1. 定义一个变量 closest 存放最终结果，初始化为 nums[0] + nums[1] + nums[2].
对于每一轮循环：
比较 mums[i] + nums[j] + noms[k] - target 的绝对值，与 closest - target 的绝对值，两者的大小。如果前者小，更新closest的值为前者的值。
比较 nums[j] + nums[k] 与 target - nums[i] 的大小，如果前者大，则将 指针 k 往前移，如果前者小，则将指针 j 往后移，若两者相等，则直接return target作为最终结果。
循环结束，closest的值即为最终结果。
3. 连续子数组的和为指定值K，求这样的子数组的个数 （Leetcode 560）
Leetcode 560
思路：
对于求连续子数组的和，想到可以先计算出数组data[i]，data[i] 存放的是从第 0 到第 i 个元素的和。
有了data[]数组之后，那么找和为 K 的连续子数组，等同于找data[i] 和 data[j] 的差值为 K 的情况，就可以。但是，这样时间效率很低，需要N方的时间复杂度。有没有更好的方法呢？有，不过比较巧妙。
对于data[i], 如果 i 之前，有某个（或者某几个）data元素的值为 data[i] - k，那么，data[i] 减去这样的元素的值，结果为K，那么这样的子数组，就是要找的子数组。这样的元素的个数，就是以nums[i]结尾，和为K的子数组，的个数。
那么，可以遍历data[]数组，同时用一个HashMap<Integer, Integer>存放data[i]出现的次数，key为data[i],value为data[i]出现的次数。
对于data[i]，先去hashmap里找key为 data[i] - k 相应的value，如果有，那么value就是以nums[i]结尾，符合条件子数组的个数。如果没有，那就没有呗。
再将data[i] 作为key，加入hashmap，值设置为1，或者增加1.
遍历时，注意有种特殊情况，data[i] - k == 0, 也就是data[i] 本身就等于k，这时，结果直接加1，同时再去hashmap里找data[i]作为key相应的value，最后也要将data[i]作为key，再放回hashmap.
整个过程处理好，是o(n)的时间复杂度。
4. 根据给定K，旋转数组（Leetcode 189）
Leetcode 189
思路：
仔细看看Input和Output，有一个很巧妙的规律。
先将数组整个反转。接着将前k个反转，后面length - k个再反转。就得到Output。
要注意 k 可能大于数组长度，所以要先对k取模。
网友评论