请选择 进入手机版 | 继续访问电脑版

LeetCode - Medium - 15. 3Sum

[复制链接]
小浣熊 发表于 2021-1-3 12:00:23 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
Topic



  • Array
  • Two Pointers
Description

https://leetcode.com/problems/3sum/
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Notice that the solution set must not contain duplicate triplets.
Example 1:
  1. Input: nums = [-1,0,1,2,-1,-4]Output: [[-1,-1,2],[-1,0,1]]
复制代码
Example 2:
  1. Input: nums = []Output: []
复制代码
Example 3:
  1. Input: nums = [0]Output: []
复制代码
Constraints:
<ul>0  0 && num != num[i - 1])) {                                int lo = i + 1, hi = num.length - 1, sum = 0 - num;                                while (lo < hi) {                                        if (num[lo] + num[hi] == sum) {                                                res.add(Arrays.asList(num, num[lo], num[hi]));                                                while (lo < hi && num[lo] == num[lo + 1])                                                        lo++;                                                while (lo < hi && num[hi] == num[hi - 1])                                                        hi--;                                                lo++;                                                hi--;                                        } else if (num[lo] + num[hi] < sum)                                                lo++;                                        else                                                hi--;                                }                        }                }                return res;        }        // 方法二:与方法一类似,用到Set去重        public List threeSum2(int[] nums) {                Set res = new HashSet();                if (nums.length == 0)                        return new ArrayList(res);                Arrays.sort(nums);                for (int i = 0; i < nums.length - 2; i++) {                        int j = i + 1;                        int k = nums.length - 1;                        while (j < k) {                                int sum = nums + nums[j] + nums[k];                                if (sum == 0)                                        res.add(Arrays.asList(nums, nums[j++], nums[k--]));                                else if (sum > 0)                                        k--;                                else if (sum < 0)                                        j++;                        }                }                return new ArrayList(res);        }        //方法三:在方法一的底子上做进一步改善        public List threeSum3(int[] nums) {                List res = new ArrayList();                if (nums.length < 3)                        return res;                Arrays.sort(nums);                for (int i = 0; i < nums.length - 2; i++) {                        if (nums > 0)                                break;                        if (i == 0 || nums != nums[i - 1]) {                                int lo = i + 1, hi = nums.length - 1, sum = 0 - nums;                                while (lo < hi) {                                        if (nums[lo] + nums[hi] == sum) {                                                res.add(Arrays.asList(nums, nums[lo], nums[hi]));                                                while (lo < hi && nums[lo] == nums[lo + 1])                                                        lo++;                                                while (lo < hi && nums[hi] == nums[hi - 1])                                                        hi--;                                                lo++;                                                hi--;                                        } else if (nums[lo] + nums[hi] < sum)                                                lo++;                                        else                                                hi--;                                }                        }                }                return res;        }}[/code] Test

  1. import static org.junit.Assert.*;import static org.hamcrest.MatcherAssert.assertThat;import static org.hamcrest.collection.IsIterableContainingInAnyOrder.containsInAnyOrder;import java.util.Arrays;import org.hamcrest.collection.IsEmptyCollection;import org.junit.Test;public class ThreeSumTest {        @Test        @SuppressWarnings("unchecked")        public void test() {                ThreeSum obj = new ThreeSum();                assertThat(obj.threeSum1(new int[] { -1, 0, 1, 2, -1, -4 }),                                containsInAnyOrder(Arrays.asList(-1, -1, 2), Arrays.asList(-1, 0, 1)));                assertThat(obj.threeSum1(new int[] {}), IsEmptyCollection.empty());                assertThat(obj.threeSum1(new int[] { 0 }), IsEmptyCollection.empty());                assertThat(obj.threeSum2(new int[] { -1, 0, 1, 2, -1, -4 }),                                containsInAnyOrder(Arrays.asList(-1, -1, 2), Arrays.asList(-1, 0, 1)));                assertThat(obj.threeSum2(new int[] {}), IsEmptyCollection.empty());                assertThat(obj.threeSum2(new int[] { 0 }), IsEmptyCollection.empty());                assertThat(obj.threeSum3(new int[] { -1, 0, 1, 2, -1, -4 }),                                containsInAnyOrder(Arrays.asList(-1, -1, 2), Arrays.asList(-1, 0, 1)));                assertThat(obj.threeSum3(new int[] {}), IsEmptyCollection.empty());                assertThat(obj.threeSum3(new int[] { 0 }), IsEmptyCollection.empty());        }}
复制代码
来源:https://blog.csdn.net/u011863024/article/details/112056667
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则


专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )