免费咨询做网站,微信开发者工具概述,建设银行门户网站,重庆城乡建设网站写在前面 最近想复习一下数据结构与算法相关的内容#xff0c;找一些题来做一做。如有更好思路#xff0c;欢迎指正。 目录 写在前面一、场景描述二、具体步骤1.环境说明2.代码 写在后面 一、场景描述 给定一个包含 n 个整数的数组 nums#xff0c;判断 nums 中是否存在三个…写在前面 最近想复习一下数据结构与算法相关的内容找一些题来做一做。如有更好思路欢迎指正。 目录 写在前面一、场景描述二、具体步骤1.环境说明2.代码 写在后面 一、场景描述 给定一个包含 n 个整数的数组 nums判断 nums 中是否存在三个元素 abc 使得 a b c 0 找出所有满足条件且不重复的三元组。
注意答案中不可以包含重复的三元组。
示例
给定数组 nums [-1, 0, 1, 2, -1, -4]
满足要求的三元组集合为
[[-1, 0, 1],[-1, -1, 2]
]二、具体步骤
1.环境说明
名称说明IntelliJ IDEA2019.2
2.代码
以下为Java版本实现
public class Lc15_threeSum {public static void main(String[] args) {
// int[] nums {-4, 4, -1, 0, 1, 2, -1, -4};int[] nums {-1, 0, 1, 2, -1, -4};System.out.println(threeSum(nums));}/*** 思路* 三数之和程序化思维确定第一个数再找另外2个数* 排序只有排序后面的滑动窗口才有意义 for循环第1个位置、while后2个位置滑动窗口** 返回值是ListList* 三数之和可以变成找三个索引位置** 由小到大进行Arrays.sort排序{-4, -4, -1, -1, 0, 1, 1, 2}* 要考虑数字重复跳过问题** 因为要找3个数相加等于0也就是要找到3个位置* for循环nums可以得到3个位置 i, li1, rnums.length-1* i确定第1个数l和r确定后2个数(while循环滑动窗口, 从两边到中间移动)** for循环条件i0, i nums.length - 2 nums[i] 0* 因为要留出另外2个数的索引所以 i nums.length -2* 如果nums[i] 大于0 往后面的数据就不需要找了题目是三数之和等于0* ** while循环(l r)* 用sum nums[i] nums[l] nums[r]和0的值进行比较* 如果小于0l* 如果大于0r--* 如果等于0i,l,r 添加到list。 l, r--继续找此处要对l和r判断去重** lr则没找到sum0的值i继续下一轮循环此处要对i进行去重判断**/private static ListListInteger threeSum(int[] nums) {ListListInteger result new ArrayList();// 排序Arrays.sort(nums);// 注意 num[i] 0就不需要找了因为是求三数之和等于0for (int i 0; i nums.length - 2 nums[i] 0;) {int l i 1, r nums.length - 1;// !!!找的是2个位置所以没有等于号while (l r) {int sum nums[i] nums[l] nums[r];if (sum 0) {result.add(Arrays.asList(nums[i], nums[l], nums[r--]));// lr指针要去重while (l r nums[l] nums[l - 1]) {l;}while (l r nums[r] nums[r 1]) {r--;}} else if (sum 0) {l;} else {r--;}}i;// i每移动一次i的值也需要去重while (i nums.length - 2 nums[i] nums[i - 1]) {i;}}return result;}
} 写在后面 如果本文内容对您有价值或者有启发的话欢迎点赞、关注、评论和转发。您的反馈和陪伴将促进我们共同进步和成长。
