java算法题解Leetcode15三数之和实例
目录
- 题目
- 解题思路
题目
给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组。 注意:答案中不可以包含重复的三元组。
示例 1:
输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
示例 2:
输入:nums = []
输出:[]
示例 3:
输入:nums = [0]
输出:[]
提示:
0 <= nums.length <= 3000
-105 <= nums[i] <= 105
解题思路
暴力解法:如果直接采用三层for循环,然后去遍历,找到三个元素,然后通过hashset或者自定义类,来去重,这样肯定超时
- 1.我们需要去想一下,如何优化算法,条件是a+b+c=0,其实我们可以优化为找到a+b=-c
- 2.三层for循环是根本,第一层和第二层循环不可避免,第三层需要可以利用a+b==-c的点来优化
- 3.如何优化?我们想到这个是一个整数数组,如果我把它排序之后,其实第二层遍历和第三层遍历,完全可以使用双指针方案来优化
- 4.第三层for循环,可以优化为一个k指针(默认位置为int k = nums.length - 1),有一个k指针从后往前,找寻nums[j] + nums[k] == nums[i]的元素
- 5.如果k--,一直往前找,依然无法找到,则无法找到
- 6.如果有满足的元素,则这时为结果元素 7.还剩余一个问题,如何去重?题目中要求我们不能有重复元素,也是利用数组已排序的点,如果数组排序之后,遍历过程中发现和前一个元素相同,则实际上就是重复了
import java.util.ArrayList; import java.util.Arrays; import java.util.List; class Solution { /** * 解题思路 * 暴力解法:如果直接采用三层for循环,然后去遍历,找到三个元素,然后通过hashset或者自定义类,来去重,这样肯定超时 * 1.我们需要去想一下,如何优化算法,条件是a+b+c==0,其实我们可以优化为找到a+b==-c * 2.三层for循环是根本,第一层和第二层循环不可避免,第三层需要可以利用a+b==-c的点来优化 * 3.如何优化?我们想到这个是一个整数数组,如果我把它排序之后,其实第二层遍历和第三层遍历,完全可以使用双指针方案来优化 * 4.第三层for循环,可以优化为一个k指针(默认位置为int k = nums.length - 1),有一个k指针从后往前,找寻nums[j] + nums[k] == nums[i]的元素 * 5.如果k--,一直往前找,依然无法找到,则无法找到 * 6.如果有满足的元素,则这时为结果元素 * 7.还剩余一个问题,如何去重?题目中要求我们不能有重复元素,也是利用数组已排序的点,如果数组排序之后,遍历过程中发现和前一个元素相同,则实际上就是重复了 * @param nums * @return */ public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> target = new ArrayList<List<Integer>>(); if (nums == null || nums.length < 2) { return target; } Arrays.sort(nums); for (int i = 0; i < nums.length; i++) { // 需要和上一次枚举的数不相同 if (i > 0 && nums[i] == nums[i - 1]) { continue; } for (int j = i + 1; j < nums.length; j++) { // 需要和上一次枚举的数不相同 if (j > i + 1 && nums[j] == nums[j - 1]) { continue; } int temp = -nums[i]; int k = nums.length - 1; while (nums[j] + nums[k] > temp && j < k) { k--; } // 如果指针重合,随着 b 后续的增加 // 就不会有满足 a+b+c=0 并且 b<c 的 c 了,可以退出循环 if (j == k) { break; } if (nums[i] + nums[j] + nums[k] == 0) { List<Integer> list = new ArrayList<Integer>(); list.add(nums[i]); list.add(nums[j]); list.add(nums[k]); target.add(list); } } } return target; } }
以上就是java算法题解Leetcode15三数之和实例的详细内容,更多关于java算法三数之和的资料请关注我们其它相关文章!
赞 (0)