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 solution set must not contain duplicate triplets.
For example, given array S = {-1 0 1 2 -1 -4},
A solution set is:
(-1, 0, 1)
(-1, -1, 2)
[分析] Two Sum的扩展版,排序输入数组,遍历数组求解。遍历 nums[k]时,找出下标 k 后面所有加和为 -nums[k]的pair,因为数组已排序,可使用两指针从两端往中间夹逼的技巧求解 two sum。注意到 k 只需遍历到相应数组元素为0时即可停止,因为三个正数的和不可能是0,另外遍历时需要跳过重复元素。
public class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (nums == null || nums.length < 3)
return result;
Arrays.sort(nums);
int N = nums.length;
for (int k = 0; k < N - 2 && nums[k] <= 0; k++) {
if (k > 0 && nums[k] == nums[k - 1])
continue;
int i = k + 1, j = N - 1;
while ( i < j) {
int sum2 = nums[i] + nums[j];
if (sum2 == -nums[k]) {
List<Integer> item = new ArrayList<Integer>();
item.add(nums[k]);
item.add(nums[i]);
item.add(nums[j]);
result.add(item);
while (++i < j && nums[i] == nums[i - 1]);
while (i <--j && nums[j] == nums[j + 1]);
} else if (sum2 < -nums[k]) {
while (++i < j && nums[i] == nums[i - 1]);
} else {
while (i <--j && nums[j] == nums[j + 1]);
}
}
}
return result;
}
}
分享到:
相关推荐
001.two-sum │ ├── information.json │ ├── README.md ├── 002.add-two-numbers │ ├── information.json │ ├── README.md ... 有一些有用的选项: Options: -r, --rule crawling rule, ...
主要介绍了LeetCode -- Path Sum III分析及实现方法的相关资料,希望通过本文能帮助到大家,需要的朋友可以参考下
3 ] } , ] , } npm start 特征 忽视问题 如果导出ignore: true则可以忽略问题 测试无序结果 如果要求您提供一系列没有特定顺序的解决方案,您可以使用辅助方法来测试您的功能。 参见49.group-anagrams.js
离线和leetcode leetcode-cli 一个享受 leetcode 的高效 cli 工具! 非常感谢 leetcode.com,一个非常棒的网站!...⦙⦙⦙⦙⦙⦙⦙⦙ ...'[3,2,4]\n7' Submit final solution! $ leetcode submit ./two-sum.cpp
离线和leetcode leetcode-cli 一个享受 leetcode 的高效 cli 工具! 非常感谢 leetcode.com,一个非常棒的网站!...⦙⦙⦙⦙⦙⦙⦙⦙ ...'[3,2,4]\n7' Submit final solution! $ leetcode submit ./two-sum.cpp
leetcode 答案 leetcode-machine-swift :SOS_button: 请帮助在Sources/leetcode-machine-swift/leetcode.swift设置所有 leetcode 问题。 :SOS_button: 在 ...利用自动补全、类型检查......Sum " , inputs : [([ 2 , 7
js代码-1. 两数之和 [简单] https://leetcode-cn.com/problems/two-sum
https://leetcode-cn.com/problems/two-sum/ 难度 : 简单 给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。...
leetcode 2 leetcode-训练 算法训练。 java $: javac hello.java java ...leetcode ...leetcode ...leetcode ...leetcode ...leetcode ...leetcode ...leetcode ...leetcode ...leetcode ...leetcode ...1.two-sum.cpp ...'[1,2,3]\n3'
leetcode 只专注于解决方案! leetcode-helper是一个单 jar 库,它使您无需为每个问题设置解决方案测试脚手架。 生成解决方案/测试框架,编译,通过一行命令进行测试。 集成了Junit ...two_sum/ │ └──
3sum leetcode-练习 算法实践 15. 3和 给定一个由 n 个整数组成的数组 nums,nums 中是否有元素 a、b、c 使得 a + b + c = 0? 在数组中找到所有唯一的三元组,其总和为零。 示例输入: [-1, 0, 1, 2, -1, -4] 示例...
leetcode编辑器leetcode-问题 自定义代码演示 leetcode 编辑器配置 代码文件名: $ ! velocityTool . camelCaseName(${question ...com.shuzijun.leetcode.editor.en ...Sum ${question.titleSlug} question t
leetcode-1-Two-Sum 这是我在 Github 的第一天。 我只是 AC leetcode 中的第一个问题。 从现在开始,我将使用Github在leetcode中记录我的生活。 我擅长 C++,但对 java 和 Python 不是很专业,我将使用最流行的 3 种...
3sum2.cpp - 3sum.cpp - BST_from_preorder_traversal.cpp - 2sum.cpp - remove_adjacent_duplicates.cpp - 子集.cpp - 子集_2.cpp - Remove_Nth_Node_From_End_of_List.cpp - invert_Binary_Tree.cpp - 对称树.cpp ...
sum: 39, 40, 216 - palindrome partitioning - regex - sudoku solver: 37 排序 - merge sort - quick sort - insertion sort - selection sort - counting sort 位操作 - find the only element which exists once...
leetcode 答案 leetcode-solution (Hot 100) leetcode 1. 两数之和题解 /** * @param {number[]} nums * @param {number} target * @return {number[]} */ // 时间复杂度为O(n^2),空间复杂度为O(1). var twoSum = ...
leetcode 答案力码 API 使用 TypeScript 编写的 Leetcode ..."two-sum" ) ; // Fetch more properties of this problem await problem . detail ( ) ; // Show problem content, test case, code snippet
3总和 中等的 4sum 中等的 从排序数组中删除重复项 简单的 删除元素 简单的 最大子阵列 简单的 移零 简单的 斐波那契数 简单的 拥有最多糖果的孩子 简单的 回溯 题号 题目 难度 电话号码的字母组合 中等的 组合和 ...
3Sum 最近的 #19。 从列表#20 的末尾删除第 N 个节点。 有效括号 #21 合并两个排序列表 #26。 从排序数组 #27 中删除重复项。 删除元素 #28。 实现 strStr() #35。 搜索插入位置 #39。 组合和#73。 设置矩阵零#74。 ...
leetcode双人赛Leetcode-火车 1. class Solution { public int[] twoSum(int[] nums, int target) { Map table = new HashMap<>(); for (int i = 0; i < nums.length; i++){ table.put(nums[i], i); } int [] ...