3 Sum

Leave a comment

November 20, 2016 by oneOokay

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: 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]
]

  1. two pointers:应该为最优方法
  2. DFS + Backtracking:肯定可以做但是杀鸡宰牛刀
  3. 2Sum的方法:也是可以做但是不最优…

这题必定是要先sort array的,然后用two pointers.难点在于:

  • two pointer的每个pointer代表什么
  • 如何移动pointers
  • 如何除重

最初想法是while loop左指针为解中的最小值,右指针为解中的最大值,用binary search找到中间的值使得和为0.这里遇到了怎么移动左右指针的难题,这样就是你不知道什么时候该移动左指针,什么时候该移动右指针.

所以其实应该一个for-loop从左往右,先确定好最小值,接着用two pointers在右侧的array里面找到一对使得这对的和加上最小值和为0.

如何移动pointers? 因为最小值是确定的,那么如果三者之和大于0的话,就移动右指针;反之移动左指针.单独移动左右指针之一的时候并不需要考虑除重.因为这种情况下都不满足和为0,不会被加入到ans里面.只有三者之和为0的时候需要除重.

如何除重?大概是这题的难点吧.

移动的值有三个:for loop移动最小值和two pointers移动另外两个值

我觉得for loop中对于nums[i]的除重貌似都可以用这个:

for (int i = 0; i < XXX; i ++) 
if (i >= 1 && nums[i] == nums[i - 1]){ continue; }

two pointers的除重基本上也就是类似这样了,在保证指针valid的情况下前后值进行比较,根据情况判断是跟前一个值相比还是跟:

while(start < end && nums[start] == nums[start - 1]){
 start ++;
 }

NOTE:

  • Arrays.asList(element1, element2, element3)
public class Solution {
 public List<List<Integer>> threeSum(int[] nums) {
 List<Integer> ans = new ArrayList<>();
 if (nums == null || nums.length < 3){
 return ans;
 }
 Arrays.sort(nums);
 for (int i = 0; i < nums.length - 2; i ++){
 if (i >= 1 && nums[i] == nums[i - 1]){ //除重1
 continue;
 }
 int start = i + 1;//start 从i+1开始
 int end = nums.length - 1;
 while (start < end){
 if (nums[start] + nums[end] + nums[i] == 0){
 ans.add(Arrays.asList(nums[i], nums[start], nums[end]));
 start ++;
 end --;
//在开始while loop之前start已经+1了,所以这里跟start的前一个值相比
 while(start < end && nums[start] == nums[start - 1]){
 start ++;
 }
//在开始while loop之前end已经-1了,所以这里跟end的后一个值相比
 while(start < end && nums[end] == nums[end + 1]){
 end --;
 }
 }else if (nums[start] + nums[end] + nums[i] < 0){
 start ++;
 }else {
 end --;
 }
 }
 }
 return ans;
 }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: