java算法题解Leetcode15三数之和实例

目录
  • 题目
  • 解题思路

题目

15. 三数之和

给你一个包含 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)

相关推荐

  • java算法题解LeetCode35复杂链表的复制实例

    目录 题目 示例 1: 示例 2: 示例 3: 示例 4: 解题思路 题目 AC 剑指 Offer 35. 复杂链表的复制请实现 copyRandomList 函数,复制一个复杂链表.在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null. 示例 1: 输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出:[[7,null],[13,0],[11,4],[10,2],[1,0]

  • java算法题解LeetCode30包含min函数的栈实例

    目录 题目 解题思路 题目 剑指 Offer 30. 包含min函数的栈 定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中,调用 min.push 及 pop 的时间复杂度都是 O(1). 示例: MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.min(); --> 返回 -3. minStack.pop();

  • java算法题解牛客BM99顺时针旋转矩阵示例

    目录 题目描述 解题思路 实践代码 解法1 解法2 题目描述 BM99 顺时针旋转矩阵 描述 有一个NxN整数矩阵,请编写一个算法,将矩阵顺时针旋转90度. 给定一个NxN的矩阵,和矩阵的阶数N,请返回旋转后的NxN矩阵. 数据范围:0<n<300,矩阵中的值满足0≤val≤1000 要求:空间复杂度 O(N^2),时间复杂度 O(N^2) 进阶:空间复杂度 O(1),时间复杂度 O(N^2) 示例1输入:[[1,2,3],[4,5,6],[7,8,9]],3返回值:[[7,4,1],[8,5

  • java算法题解Leetcode15三数之和实例

    目录 题目 解题思路 题目 15. 三数之和 给你一个包含 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 <=

  • IOS 算法 三数之和求解问题

    目录 IOS 算法三数之和求解问题 1.三数求和简单介绍 2.代码 IOS 算法三数之和求解问题 1.三数求和简单介绍 对于一个整数的数组, 是否存在a, b, c 使得 a + b + c = 0, 返回a b c 数组,相同数组只返回一个,: 例如: [-1, -2, 6, 5, 0, 1, 2, -1, -1] 返回 [[-1, 0, 1], [-2, 0, 2], [-1, -1, 2]] 关键点: ① 找到和为0的三个数 ② 去除相同项, 比如: 上面的数组 其实 [-1, 0, 1]

  • 关于PHP求解三数之和问题详析

    三数之和 给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组. 注意:答案中不可以包含重复的三元组. 示例: 给定数组 nums = [-1, 0, 1, 2, -1, -4], 满足要求的三元组集合为: [ [-1, 0, 1], [-1, -1, 2] ] 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/3sum 解题思路

  • Java实现LeetCode（两数之和）

    给定一个整数数组和一个目标值,找出数组中和为目标值的两个数. 你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用. 示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回[0, 1] 思路一:最直接的思维,两次遍历查询,时间复杂度O(N*N). 代码: public static int[] twoSum1(int[] nums, int target) { int[] label =

  • Java C++题解 leetcode第k个数实例

    Java C++题解 leetcode第k个数实例

    目录 题目要求 思路一:小根堆 Java C++ 思路二:多路归并[多指针] Java C++ Rust 总结 题目要求 思路一:小根堆 中文题目描述不太清晰,但其实由题目可以发现,当x满足条件时,3x.5x.7x分别也都满足条件. 将满足条件的数依次放入优先队列存放用于后续计算,由于每次要取待计算队列中最小的数x,所以定义小根堆: 弹出x,计算3x.5x.7x并入队: 用一个哈希表记录防止重复入队. 每次取数(pop)时进行计数,到第k次结束,当前队首即为答案. Java <学到了> 1L也

  • Python三数之和的实现方式

    目录 三数之和题目描述 思路 Python3代码 三数之和题目描述 给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c , 使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组. 答案中不允许包含重复的三元组. 示例: 给定数组 nums = [-1, 0, 1, 2, -1, -4], 满足要求的三元组集合为: [   [-1, 0, 1],   [-1, -1, 2] ] 思路 1. 首先将数组排序,可以利用Python内置函数,也可

  • java面试题解LeetCode27二叉树的镜像实例

    目录 正文 解题思路 方法一:递归法 方法二:辅助栈(或队列) 正文 LeetCode27. 二叉树的镜像 请完成一个函数,输入一个二叉树,该函数输出它的镜像. 例如输入: 4 /2 7 / \ /1 3 6 9 镜像输出: 4 /7 2 / \ /9 6 3 1 示例 1: 输入:root = [4,2,7,1,3,6,9] 输出:[4,7,2,9,6,3,1] 限制: 0 <= 节点个数 <= 1000 解题思路 方法一:递归法 根据二叉树镜像的定义,考虑递归遍历(dfs)二叉树,交换每个

  • java算法之二分查找法的实例详解

    java算法之二分查找法的实例详解 原理 假定查找范围为一个有序数组(如升序排列),要从中查找某一元素,如果该元素在此数组中,则返回其索引,否则返回-1.通过数组长度可取出中间位置元素的索引,将其值与目标值比较,如果中间位置元素值大于目标值,则在左部分进行查找,如果中间位置值小于目标值,则在右部分进行查找,如此循环,直到结束.二分查找算法之所以快是因为它没有遍历数组的每个元素,而仅仅是查找部分元素就能找到目标或确定其不存在,当然前提是查找范围为有序数组. Java的简单实现 package me

  • C++实现LeetCode（三数之和）

    Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. Note: Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c) The solut

随机推荐