首页 > 代码库 > [LeetCode]3Sum,解题报告
[LeetCode]3Sum,解题报告
题目
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.
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.
思路
开始想用深搜解决,后来发现用深搜很难保证结果没有重复的结合,因此采用排序+双指针固定解决思路,同时增加去除重复的判断机制
AC代码
public class Solution { public List<List<Integer>> threeSum(int[] num) { List<List<Integer>> res = new ArrayList<List<Integer>>(); if (num.length < 3) { return res; } Arrays.sort(num); for (int i = 0; i < num.length - 2; i++) { // avoid duplicate if (i == 0 || num[i] > num[i - 1]) { int start = i + 1; int end = num.length - 1; while (start < end) { int stand = num[i] + num[start] + num[end]; if (stand == 0) { ArrayList<Integer> tmp = new ArrayList<Integer>(); tmp.add(num[i]); tmp.add(num[start]); tmp.add(num[end]); res.add(tmp); start++; end--; //avoid duplicate while (start < end && num[start] == num[start - 1]) { start ++; } while (start < end && num[end] == num[end + 1]) { end --; } } else if (stand > 0) { end--; } else { start++; } } } } return res; } }
后记
在家呆了5天就要回帝都去阿里上班了,不舍得爸妈,努力工作,争取早点财务自由!多花时间陪陪家人。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。