当前位置: 首页> 科技> 数码 > 浙江网站建设技术公司_建网站的网络公司的名称以及服务_免费网站制作_十堰seo

浙江网站建设技术公司_建网站的网络公司的名称以及服务_免费网站制作_十堰seo

时间:2025/7/11 11:47:52来源:https://blog.csdn.net/qq_14815605/article/details/143005427 浏览次数:0次
浙江网站建设技术公司_建网站的网络公司的名称以及服务_免费网站制作_十堰seo

LeetCode 15. 三数之和

题目描述

给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 abc 使得 a + b + c = 0?请你找出所有和为 0 且不重复的三元组。

注意:

  • 答案中的三元组可以按任意顺序组织。
  • nums 中,除了同一个三元组中的元素可以重复外,不可以有重复的三元组。

示例 1:

输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]

示例 2:

输入:nums = []
输出:[]

示例 3:

输入:nums = [0,0,0]
输出:[[0,0,0]]

Java 实现解法

方法一:排序 + 双指针
class Solution {public List<List<Integer>> threeSum(int[] nums) {Arrays.sort(nums); // 首先对数组进行排序List<List<Integer>> result = new ArrayList<>();for (int i = 0; i < nums.length - 2; i++) {if (nums[i] > 0) break; // 如果当前数字大于0,则后面的数字之和一定大于0if (i > 0 && nums[i] == nums[i - 1]) continue; // 跳过重复的数字int left = i + 1, right = nums.length - 1;while (left < right) {int sum = nums[i] + nums[left] + nums[right];if (sum < 0) {left++;} else if (sum > 0) {right--;} else {result.add(Arrays.asList(nums[i], nums[left], nums[right]));while (left < right && nums[left] == nums[left + 1]) left++; // 跳过重复的数字while (left < right && nums[right] == nums[right - 1]) right--; // 跳过重复的数字left++;right--;}}}return result;}
}

解题思路

  • 排序:首先对数组进行排序,这样可以通过一次遍历来找到所有可能的三元组,并且可以方便地跳过重复的解。
  • 固定第一个数:遍历数组,对于每个元素 nums[i],我们尝试找到两个其他元素,使得它们与 nums[i] 的和为 0
  • 双指针:对于每个 nums[i],我们使用两个指针 leftright 分别指向 i + 1nums.length - 1。这样,我们可以在这个范围内寻找和为 -nums[i] 的两个数。
  • 跳过重复解:如果在数组中找到了相同的数字,跳过它们以避免重复的三元组。
  • 更新指针:如果三数之和小于 0,则移动 left 指针;如果大于 0,则移动 right 指针;如果等于 0,则找到了一个解,并更新指针跳过重复的数字。

这种方法的时间复杂度是 O(n^2),其中 n 是数组 nums 的长度。因为我们对数组进行了排序,然后进行了两层嵌套循环。空间复杂度是 O(1),除了输入数组和输出列表外,我们没有使用额外的空间。

注:来源leetcode网站

关键字:浙江网站建设技术公司_建网站的网络公司的名称以及服务_免费网站制作_十堰seo

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: