1 题目
LeetCode 第 15 题 https://leetcode-cn.com/problems/3sum/ , 难度中等, 题目描述:
给定一个包含 n 个整数的数组 nums, 判断 nums 中是否存在三个元素 a,b,c , 使得 a + b + c = 0 ? 找出所有满足条件且不重复的三元组.
注意: 答案中不可以包含重复的三元组.
2 解法
什么也不管先来个 O(n3):
- for(int i=0;i<nums.length;++i)
- {
- for(int j=i+1;j<nums.length;++j)
- {
- for(int k=j+1;k<nums.length;++k)
- {
- if(nums[i]+nums[j]+nums[k] == 0)
- {
- ArrayList<Integer> arrayList = new ArrayList<>();
- arrayList.add(nums[i]);
- arrayList.add(nums[j]);
- arrayList.add(nums[k]);
- result.add(arrayList);
- }
- }
- }
- }
well.
3 优化
上面暴力算法的思想就是单纯三个循环, 优化的方法可以考虑降低一个循环, 使用 "双指针" 的思想, 首先对数组进行排序, 然后一开始固定一个数, 然后让两个指针一个指向这个数的右区间的起点, 一个指向终点, 不断计算这三个值的和, 根据得出的和移动左指针或者右指针, 一共三种情况:
和等于 0, 同时移动左右指针, 两者向中间方向移动.
和大于 0, 说明取值过大, 需要把右指针向左移动.
和小于 0, 说明取值过小, 需要把左指针向右移动.
基于以上的三种情况, 写出了如下代码:
- List<List<Integer>> result = new ArrayList<>();
- if (nums.length == 3 && nums[0] + nums[1] + nums[2] == 0)
- result.add(Arrays.asList(nums[0], nums[1], nums[2]));
- else if (nums.length> 3)
- {
- Arrays.sort(nums);
- Set<List<Integer>> resultSet = new HashSet<>();
- for (int i = 0; i <nums.length - 2 && nums[i] <= 0; ++i)
- {
- int left = i + 1;
- int right = nums.length - 1;
- while (left < right)
- {
- int sum = nums[i] + nums[left] + nums[right];
- if (sum == 0)
- {
- if (!resultSet.contains(Arrays.asList(nums[i], nums[left], nums[right])))
- resultSet.add(Arrays.asList(nums[i], nums[left], nums[right]));
- --right;
- ++left;
- }
- else if (sum> 0)
- --right;
- else
- ++left;
- }
- }
- result.addAll(resultSet);
- }
首先判断数组的长度是否大于等于 3, 小于 3 的话直接返回一个空 List, 等于 3 判断是否这三个数之和为 0, 大于 3 的话, 首先排序, 接着需要确保被确定的相对不移动的数为负数, 这样的话剩下两个数的和才有可能为正数, 否则的话会造成全部都是正数还要进行判断的局面. 接着计算 left 指针与 right 指针的值, 一直判断直到两指针相遇.
4 提交
AC!
5 完整代码
https://github.com/2293736867/ACEveryDay
码云 https://gitee.com/imykr/ACEveryDay
来源: http://www.bubuko.com/infodetail-3392911.html