LeetCode 015 三数之和
有勇气的牛排
22
算法
2025-08-07 22:09:18
题目
标签：数组、双指针、排序
给你一个整数数组 nums，判断是否存在三元组 [nums[i], nums[j], nums[k]]满足 i != j、i != k 且 j != k，同时还满足 nums[i] + nums[j] + nums[k] == 0。请你返回所有和为 0 且不重复的三元组。
注意：大安中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
示例 2：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。
示例 3：
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。
提示：
3 <= nums.length <= 3000-105 <= nums[i] <= 105
2025-02-25 拼多多 原题
问题分析
在数组 nums 中，找出所有 不重复 的三元组 [a, b, c]，使得：
a+b+c=0
难点：
- 如何高效找到三元组（不能用O(n³)暴力枚举）。
- 如何避免重复结果。
排序+双指针
-
先排序数组 → 方便去重和使用双指针。
-
遍历数组，固定一个数 nums[i]，然后用 左右指针 在剩余部分找两个数，使得：
nums[i]+nums[l]+nums[r]=0
-
具体步骤：
- 如果
nums[i] > 0，直接 break（因为数组已排序，三数和不可能为 0）。
- 如果
i > 0 且 nums[i] == nums[i-1]，跳过（避免重复三元组）。
- 设
l = i+1, r = n-1：
- 如果和大于 0 →
r--
- 如果和小于 0 →
l++
- 如果和等于 0 → 记录结果，并移动
l, r，同时跳过重复元素。
继续遍历直到结束。
<h2><a id="_0"></a>题目</h2>
<p>标签：数组、双指针、排序</p>
<p>给你一个整数数组 <code>nums</code>，判断是否存在三元组 <code>[nums[i], nums[j], nums[k]]</code>满足 <code>i != j</code>、<code>i != k</code> 且 <code>j != k</code>，同时还满足 <code>nums[i] + nums[j] + nums[k] == 0</code>。请你返回所有和为 <code>0</code> 且不重复的三元组。</p>
<p><strong>注意</strong>：大安中不可以包含重复的三元组。</p>
<p><strong>示例 1：</strong></p>
<pre><div class="hljs"><code class="lang-shell">输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
</code></div></pre>
<p><strong>示例 2：</strong></p>
<pre><div class="hljs"><code class="lang-shell">输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。
</code></div></pre>
<p><strong>示例 3：</strong></p>
<pre><div class="hljs"><code class="lang-shell">输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。
</code></div></pre>
<p><strong>提示：</strong></p>
<ul>
<li><code>3 <= nums.length <= 3000</code></li>
<li><code>-105 <= nums[i] <= 105</code></li>
</ul>
<p>2025-02-25 拼多多 原题</p>
<h2><a id="_48"></a>问题分析</h2>
<p>在数组 <code>nums</code> 中，找出所有 <strong>不重复</strong> 的三元组 <strong>[a, b, c]</strong>，使得：</p>
<p>a+b+c=0</p>
<p>难点：</p>
<ol>
<li>如何高效找到三元组（不能用O(n³)暴力枚举）。</li>
<li>如何避免重复结果。</li>
</ol>
<h2><a id="_59"></a>排序+双指针</h2>
<ol>
<li>
<p><strong>先排序</strong>数组 → 方便去重和使用双指针。</p>
</li>
<li>
<p>遍历数组，固定一个数 <code>nums[i]</code>，然后用 <strong>左右指针</strong> 在剩余部分找两个数，使得：</p>
<p>nums[i]+nums[l]+nums[r]=0</p>
</li>
<li>
<p>具体步骤：</p>
<ul>
<li>如果 <code>nums[i] > 0</code>，直接 break（因为数组已排序，三数和不可能为 0）。</li>
<li>如果 <code>i > 0 且 nums[i] == nums[i-1]</code>，跳过（避免重复三元组）。</li>
<li>设 <code>l = i+1</code>, <code>r = n-1</code>：
<ul>
<li>如果和大于 0 → <code>r--</code></li>
<li>如果和小于 0 → <code>l++</code></li>
<li>如果和等于 0 → 记录结果，并移动 <code>l, r</code>，同时跳过重复元素。</li>
</ul>
</li>
</ul>
<p>继续遍历直到结束。</p>
</li>
</ol>
评论区