和为 s 的两个数  

和为s的两个数

---

  题目描述  

  解法一：暴力枚举  

暴力枚举，先固定一个数，然后让这个数和另一个数匹配相加，

如果当前的数 + 所有剩余的数 = target，则返回这两个数，否则固定下一个数；

所以暴力枚举只需要两层 for() 即可，但是这种解法实在太慢了，题目中给的是一个有序的数组，我们要利用数组有序的特性

---

  解法二：利用单调性  

利用单调性，使用双指针算法解决问题

先固定数组的首尾元素，固定好后，让两个数相加一下，看看能否使用单调性进行优化。

先不管 target 等于多少，这两个数之和 sum 无非就是三种情况

注意：sum 指的是 left 和 right 指向的数组元素之和

1. sum < target
2. sum > target
3. sum = target

对比暴力枚举，利用单调性，使用双指针的算法的时间复杂度得到大大的优化；

暴力枚举需要拿固定的数，和所有剩余的数相加，但是解法二只需要让固定的数相加一次即可，就能判断是否舍弃当前固定的数了 

  时间复杂度  

解法一 O(N^2)，解法二O(N)

---

  编写代码  

报错原因：

没有返回值，我们已经写了 return 语句，那么为什么编译器还会认为我们没有返回值呢？

我们必须保证所以的路径都要有返回值，而在上述代码，编译器不会管 while 语句中的 return 是否被执行，而是会考虑 只有 return 前的else 成立才会有返回值；

对于其他路径，如 else 不成立时，那么这个函数就没有返回值了，所以为了照顾编译器，强行返回一个值，就是告诉编译器一定会有返回值的：

---

  快乐数   

快乐数

---

题目描述

第一种情况

 

return true

---

第二种情况

---

这个数在定义的过程中，会进入到一个没有 1 的环中，并且无限在环中循环，始终变不到 1

return false

---

  题目解析  

---

可以回忆OJ题：判断链表是否有环 ；

对于一个数，经过快乐数的定义变换后，是一定会成环的，并且题目也给出了提示；

如果题目没给提示，我们就需要验证是否会出现不成环的情况；其实是一定会成环的；

 

证明快乐数一定成环

---

 鸽巢原理（抽屉原理）：n个巢，n+1 只鸽子，至少有一个巢，里面的鸽子数大于1

---

这道题的数据范围

---

最终，2^31 -1 的结果是一个10位整数，所以：

---

2^31 -1 < 999999999

---

快乐数转换(2^31 -1 ) < 快乐数转换（999999999）=81*10=810

---

所以快乐数的值的区间一定是[ 0，810 )，我们的巢穴出来了，我们随便找一个数，让他经过快乐数转换 811 次，转换的数一定是在 [ 0，810 )区间内的，在 转换 811 次之内，一定会出现重复的数，也就是一定会成环的。

所以对于这题，我们只需判断环中是否为1 ，来决定最终返回的boolean值

---

  解法：快慢双指针   

这里的指针并不是真正的指针，只是一种指针思想，在这题中，我们把变化过程中的数，抽象成指针；

---

• 1. 定义快慢指针；
• 2. 慢指针每次向后移动一步，快指针每次向后移动两步；
• 3. 对于判断链表是否有环，我们看的是快慢双指针最终能否相遇；
• 4. 对于快乐数，是一定会成环的，快慢双指针一定会相遇，我们只需要判断相遇点的值是否为1 ；

---

  编写代码  

---

因为每一次快乐数转换，都需要 求和 这个数的 每一位数 的平方，因此我们可以把这个过程封装成一个方法 bitSum() ，返回 n 这个数每一位上的平方和

---

  盛最多水的容器   

 盛最多水的容器

---

  题目解析   

 

 right - left = 两根柱子之间的格子个数 = 宽度，返回 S 即可

---

  解法一：暴力枚举  

通过两层 for 循环，先让 left 固定左边的柱子， right 依次枚举右边的柱子；一轮枚举后，让 left 固定第二根柱子；但是这种做法是超时的；

---

  解法二：对撞指针  

算法原理

---

首先让 left 和 right 指向 6 和 4 ； 

此时如果让 right 固定的是4，让left 向内枚举那么 wide 一直减小

在让 right 固定4，left 向内枚举时，会碰到三种情况：

1. height[left] < height [right]；
2. height[left] = height [right]；
3. height[left] > height [right];

对于第一种情况，此时根据木桶原理，容器的高度是减小的，所以 S 减小；

第二种情况和第三种情况，根据木桶原理，容器的高度都是不变的，但是 wide 一直在减小；

---

所以无论是三种情况中的哪一种，向内枚举的 V 一直都是减小的；

所以拿 min( height[left] , height [right]) * wide 得到的 S，

如果固定其中任意一个指针，向内枚举一次，发现 S 减小，那就可以大胆的 舍弃当前 left 和 right 两个指针的较小值，固定较大值。

根据上面的思想，我们可以先固定 left 指向的1，让 right 向内枚举一次，得到的 S 是在减小的，因此可以大胆的舍弃 1，让left++；

 此时，我们可以尝试着把 right 指向的 7干掉，让 right--，因为如果固定 7，那拿left 向内枚举，通过木桶原理，得到的 S 一直都是在减小的；

 如果当前 left 和 right 是相同的，那么舍弃谁都可以，因为根据木桶原理，向内枚举体积都是在减小的；

---

  总结   

---

• S 是由宽度和木桶的短板决定的，在向内枚举时，优先向内移动两个指针中，指向较小值的指针；
• 每次枚举都求出对应的 S ，直到 left 和 right 对撞，返回这几次枚举中，S 的最大值

---

  时间复杂度  

解法一 O(N^2)；解法二 O(N)

---

  编写代码  

---

---

  三数之和   

三数之和(这个题一定一定一定要画图，空想会错很多，自己把这个题的代码写出来)

---

题目描述

---

我们根据题意，可以选出三组和为0的三元组，但是输出结果只要两组数：

所以是因为，第一组和第二组，选出的三元组，虽然顺序不一样，但是三元组的元素一样；

所以不可以包含重复三元组的意思，就是三元组的顺序不重要，只要的是两组三元组的元素不能完全一样。

这道题的难点是去重操作，我们先来想解法 

解法一：先排序 + 暴力枚举 + 利用 set 去重

定义三层 for 循环，把能三个数之和等于0的，所有符合条件的三元组求出来，再对求出的组合去重；

去重操作，可以先把三元组从小到大排序，排好序之后再一 一 比对；

但是，如果在一个 length 非常大的数组中，找到了多对重复的，符合条件的三元组，那么一个一个找会非常麻烦。所以我们可以先把整个数组进行排序，然后再规定从左往右的顺序，进行所有三元组的枚举：

如果我们再一次找符合条件的三元组，就会发现找到的三元组已经是排好序的了；

比起刚刚的像刚刚没对数组排序，而是先找三元组，再对三元组排序 ；先对整个数组排序，再枚举所有三元组，更利于我们的查重操作

我们再利用 Java 中的 Set 集合，把所有得到的三元组，放入 HashSet 中，就会对数组去重，并且这是建立在排序整个数组，得到所有符合题意的三元组，才可以完美利用上 Set 的特性。

把所有三元组放入 Set 中，再把 Set 的结果拿出来作为返回值。

暴力枚举的时间复杂度：O( N^3 )，三层 for循环，去重操作针对的是有限个数的三元组，所以去重操作的时间复杂度可以忽略不记。

---

解法二：排序 + 双指针

用双指针，可以让时间复杂度降维，是非常优秀的算法，来看下面例子：

该数组已经排好序，利用暴力枚举时，我们是先固定一个数，然后在剩余区间中找到两个数组成符合题意的三元组

 固定一个数，在剩余的数字，并且是有序的数字中，利用双指针快速找到符合题意的两个数。

 处理细节问题：

去重；并且在上图的 left 和 right 区间中，有多对组合能相加凑出4，我们要把他们全部都找到；

1. 不漏
2. 去重 
3. 避免指针越界(在去重过程中会出现越界)

这三步操作是本题最重要的

否则

此时 left + right =4，此时 i，left，right拼接成第一对符合题意的三元组；但是我们还要继续这个过程，直到固定当前 i指针 的情况下，left 和 right 相遇。

所以不漏的操作，需要注意：

找到一种结果，不要让 left 和 right 停下来，继续缩小两个指针的区间 。

当然，如果在找到如上图的组合后，后面重复的 0 和 4 就不需要继续枚举了，所以我们去重，是要在找到一种结果之后，left  和  right  要跳过重复元素：

此时 i指针固定的第一个数的所有情况都已经枚举完毕，i++，此时我们发现，i指针 由指向了 -4：

又会出现重复的计算，因此我们去重要注意两个地方

• left 和 right 的去重
• 当使用完一次双指针算法之后，i 指针 也需要跳过重复元素

紧扣这两个情况，就能处理好去重操作

去重完后，我们还要处理双指针越界的情况：

通过刚刚的去重思想，来遍历上面的组合，会让双指针越界，因此我们在移动 i，left，right指针，来避免重复元素的时候，一定要处理指针越界的问题，我们结合代码，来讲解处理越界的情况。

还有一个小细节：

---

 从煮啵写的代码来看，可以发现数据结构的基础很差~~~~

完整代码 

修改： 下面i++，for循环就不要 i++了，不然会跳过要固定的下一个a

 时间复杂度：O(N^2)

空间复杂度：用到了Arrays.sort()，快排，是递归产生的空间消耗，O(logN)

---

  四数之和 

四数之和

---

解法一：排序 + 暴力枚举 + 利用 set 去重

解法二：排序 + 双指针

1. 依次固定一个数 a
2. 在 a 后面的区间内，找到“三数之和”思想 得到的三个数，使这三个数的和等于 target - a 即可
3. 依次固定一个数 b
4. 在 b 后面的区间内，利用“双指针”找到两个数，舍得这两个数的和等于“target - a - b”即可

 

整体思路，两层 for 循环中套一个双指针算法，这只是整体思路，还需处理细节问题：

处理细节问题：

(1)去重:

• left 和 right 要跳过重复的数
• 利用完双指针，b要跳过重复元素
• 利用“三数之和”后，a要跳过重复元素

(2)不漏（双指针在找到一组符合条件的数时，继续缩小区间）

编写代码：

解析：在计算的时候，会有溢出的风险，也就是计算结果和预期结果不符合：

 

时间复杂度：O(N^3)

空间复杂度：O(logN)，和三数之和的原因相同

---