首页 > 代码库 > 【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.
For example, given array S = {-1 0 1 2 -1 -4}, A solution set is: (-1, 0, 1) (-1, -1, 2)
题解:把3Sum转换成2Sum,然后解决2Sum问题。
对于num中任意一个数num[i],我们要在i+1~num.length-1之间寻找两个数使得它们的和为0-num[i]。
而寻找两个数使得它们的和为0-num[i],我们可以设定两个指针start和last,我们知道在start+1~last之间我们要寻找的数是0-num[i]-num[start],这样三个数的和就是0了。所以如果
- last所指向的数比0-num[i]-num[start]大,我们把last指针往前移动;
- 如果比0-num[i]-num[start]小,我们把start指针往后移动(last指针不动是因为我们已经搜索过了可能和last指针后面组成答案的数,这些数在start之前);
- 如果相等,就把num[i],num[start]和num[last]三个数依次放在list中作为一组答案。然后越过start后面和start相等的数,继续循环。
图示如下:
例如题目的数组排序后得到{-4,-1,0,1,2},当i指向-1的时候,我们需要在{0,1,2}之中找到两个数和为0-(-1)=1,把start指向0,last指向2,那么我们接下来要利用last找到1,last目前指向2,比需要的数1大,所以前移last,wala,我们找到了需要的1,同时找到了一组答案[-1,0,1]。
去重的工作十分简单,除了上述说的越过start后面和start相等的数外,在最外层的for循环的时候,如果num[i] = num[i-1],那么也可以越过i。
最后代码如下:
1 public class Solution { 2 public List<List<Integer>> threeSum(int[] num) { 3 List<List<Integer>> answer = new ArrayList<List<Integer>>(); 4 if(num == null || num.length == 0) 5 return answer; 6 Arrays.sort(num); 7 8 for(int i = 0;i < num.length;i++){ 9 //remove duplicates10 if(i != 0 && num[i] == num[i-1])11 continue;12 int twoSum = 0 - num[i];13 int start = i + 1;14 int last = num.length-1;15 while(start < last){16 int OneSum = twoSum - num[start];17 //Found one solution18 if(num[last] == OneSum){19 ArrayList<Integer> result = new ArrayList<Integer>();20 result.add(num[i]);21 result.add(num[start]);22 result.add(num[last]);23 answer.add(result);24 start++;25 last--;26 //remove duplicates27 while(start < last && num[start] == num[start-1])28 start++;29 }30 else if(num[last] > OneSum)31 {32 last--; 33 }34 else{35 start++;36 }37 }38 }39 40 return answer;41 }42 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。