题目 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.
思路 开始想用深搜解决，后来发现用深搜很难保证结果没有重复的结合，因此采用排序+双指针固定解决思路，同时增加去除重复的判断机制
AC代码
public class Solution {
public List
> threeSum(int[] num) {
List
> res = new ArrayList
>(); 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
tmp = new ArrayList
(); 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天就要回帝都去阿里上班了，不舍得爸妈，努力工作，争取早点财务自由！多花时间陪陪家人。
|