LeetCode的练习题目为：《15. 三数之和》
原题链接：三数之和 给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
自我思考
拿到题目的第一刻就想到了用3层for循环组成所有出现的情况，然后对出现的情况进行去重处理。得出以下代码：
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> li = new ArrayList<List<Integer>>();
List<String> keyList = new ArrayList<String>();
Arrays.sort(nums);
// 由于对于0 0 0 0 0 。。。这种情况处理不当，增加了一个对象来确定是否出现了多次 0 0 0 的情况
int oneZero = 0;
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
for (int f = j + 1; f < nums.length; f++) {
if (nums[i] + nums[j] + nums[f] == 0) {
if (oneZero == 1 && nums[i] == 0 && nums[j] == 0 && nums[f] == 0) {
break;
} else {
List<Integer> lin = new ArrayList<Integer>();
lin.add(nums[i]);
lin.add(nums[j]);
lin.add(nums[f]);
if (!keyList.contains(lin.toString())) {
li.add(lin);
keyList.add(lin.toString());
}
if (nums[i] == 0 && nums[j] == 0 && nums[f] == 0) {
oneZero = 1;
}
}
break;
}
}
}
}
return li;
}
自然以上代码也是修正了好几次的产物，不过好歹算是通过了。然后根据原始路径想自己写的这个版本为什么这么差劲-_-..然后去看评论区 有木有大哥拯救。然后发现了一篇 Concise O(N^2) Java solution 大哥的写法是这样(大部分版本都和下面这个类似):
public List<List<Integer>> threeSum(int[] num) {
// 将数组变成有序数组，便于后面的循环和去重操作
Arrays.sort(num);
List<List<Integer>> res = new LinkedList<>();
// 倒数后俩位 没有三个数来组成结果 跳过
for (int i = 0; i < num.length-2; i++) {
// 第一次直接进入，如果是后续 判断是否出现过，出现则跳过，保证最少循环。
if (i == 0 || (i > 0 && num[i] != num[i-1])) {
// （取当前+1 下标） （取倒数 下标） （取 0-当前值）
int lo = i+1, hi = num.length-1, sum = 0 - num[i];
// while条件为 开始下标 < 倒数下标 逻辑为 从当前坐标开始 取 后一位 从最后 取一个坐标 开始像中间靠拢 跳过重复值
while (lo < hi) {
// 结果相加 等于 sum 则证明 其三个下标对应的值为0
if (num[lo] + num[hi] == sum) {
res.add(Arrays.asList(num[i], num[lo], num[hi]));
// 寻找下一个 开始下标
while (lo < hi && num[lo] == num[lo+1]) lo++;
// 寻找下一个 倒数下标
while (lo < hi && num[hi] == num[hi-1]) hi--;
lo++; hi--;
}
// 如果相加值小于 则增大总和 所以推动 lo ++ ，反之减少 hi --
else if (num[lo] + num[hi] < sum) lo++;
else hi--;
}
}
}
return res;
}
想一个问题，为什么我的脑回路想到的是三层for循环呢- - 而速度快的写的都是for循环嵌套 while循环进行寻找。
我在想是我脑壳出了什么问题吗- -。。。还是下次遇到的时候，我也可以这样写了呢- -。。。。。。。。。
想到了之前极客时间里面的教程，讲递归的时候讲到：
首先是递归公式
其次是终止条件
所以目前来看，是由于我研究题目没有深刻，没有找到这个问题的核心点。
找三个值相加为0
去掉重复的组合
尽量减少循环次数（减少时间复杂度）
一开始想问题过于简单，只注重于前俩点，而且一开始的思路为什么直接想的就是三层for循环呢？？？ 瓜皮三连，重点在于减少for循环的次数。
许可协议: 知识共享署名-非商业性使用 4.0 国际许可协议
