LeetCode - Medium - 15. 3Sum

妖狐艹你老母 2023-01-01 07:00 157阅读 0赞

## Topic ##

*  Array
 *  Two Pointers

## Description ##

[https://leetcode.com/problems/3sum/][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**:

Input: nums = [-1,0,1,2,-1,-4]
    Output: [[-1,-1,2],[-1,0,1]]

**Example 2**:

Input: nums = []
    Output: []

**Example 3**:

Input: nums = [0]
    Output: []

Constraints:

*  0 <= nums.length <= 3000
 *  \-10⁵ <= nums\[i\] <= 10⁵

## Analysis ##

方法一：

1.  首先将数组从左到右升序排序。
2.  接下来动用三个指针，用一指针a先固定一元素，然后指针b初始位置为a的右一位，指针c初始位置数组尾元素，
3.  b、c两指针向中间夹逼寻找出这两指针所指元素之和等于a指针所指元素 \* -1，期间忽略重复元素，寻找到则将结果添加至List。
4.  当b、c两指针相遇，指针a向右移动一位，跳到步骤2.，直到指针a移动到数组倒数第二位。

方法二：与方法一类似，用到Set去重。

方法三：在方法一的基础上，进一步完善：

1.  方法体内第一句后添加防御性代码`if (nums.length < 3) return res;`。
2.  for循环中第一语句前插入一句`if (nums[i] > 0) break;`。这是因为数组已经是从左到右升序的，如果第一个数大于0，就不可能在接下来的元素中寻找出两元素之和小于0的。
3.  将`if (i == 0 || (i > 0 && num[i] != num[i-1]))`中的`i > 0`是不必要的，将其移除。

## Submission ##

import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.HashSet;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Set;
    
    public class ThreeSum { 
    
    	// 方法一：
    	public List<List<Integer>> threeSum1(int[] num) { 
    		Arrays.sort(num);
    		List<List<Integer>> res = new LinkedList<>();
    		for (int i = 0; i < num.length - 2; i++) { 
    			if (i == 0 || (i > 0 && num[i] != num[i - 1])) { 
    				int lo = i + 1, hi = num.length - 1, sum = 0 - num[i];
    				while (lo < hi) { 
    					if (num[lo] + num[hi] == sum) { 
    						res.add(Arrays.asList(num[i], 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<List<Integer>> threeSum2(int[] nums) { 
    		Set<List<Integer>> 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[i] + nums[j] + nums[k];
    				if (sum == 0)
    					res.add(Arrays.asList(nums[i], nums[j++], nums[k--]));
    				else if (sum > 0)
    					k--;
    				else if (sum < 0)
    					j++;
    			}
    
    		}
    		return new ArrayList<>(res);
    	}
    
    	//方法三：在方法一的基础上做进一步改善
    	public List<List<Integer>> threeSum3(int[] nums) { 
    		List<List<Integer>> res = new ArrayList<>();
    		if (nums.length < 3)
    			return res;
    		Arrays.sort(nums);
    		for (int i = 0; i < nums.length - 2; i++) { 
    			if (nums[i] > 0)
    				break;
    			if (i == 0 || nums[i] != nums[i - 1]) { 
    				int lo = i + 1, hi = nums.length - 1, sum = 0 - nums[i];
    				while (lo < hi) { 
    					if (nums[lo] + nums[hi] == sum) { 
    						res.add(Arrays.asList(nums[i], 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;
    	}
    }

## Test ##

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_leetcode.com_problems_3sum]: https://leetcode.com/problems/3sum/