[Leetcode][015] 3Sum (Java)

浏览数：28 / 时间：2015年06月08日

题目在这里: https://leetcode.com/problems/3sum/

【标签】 Array; Two Pointers

【个人分析】

老实交待，这个题卡半天，第一次做不会，抄别人的。过了很久，第二次做，还是不会……。好几次都是Time Limited Error。在看过正确答案之后，才知道是用的Two Pointers + sort 做的优化。

　　怎么优化？简单说，就是通过排序 + 跳过重复(利用Two Pointers) 来达到题目中避免 duplicates的要求。

　　核心思路：我们给最终的由3个数组成的小数组叫 triplet。

1. 先锁定triplet中的第一个数字的index为 i (Line 12),

2. 然后我们希望从 [ nums[i + 1], nums[end]] 中找到两个数字，使得两个数字的和为 (0 - nums[i])

　　关键步骤：1. 在锁定第一个数字index的时候，跳过所有重复的数字 (Line 16处)。直到我们找到下一个不重复的数字作为triplet中的第一个数字

2. 在从[nums[i + 1], nums[end]]中找两个数字的时候，利用left pointer, right pointer。如果 left, right两个数的和比 twoSumTarget (Line 39)

小的话，只能通过将left pointer向右移动，来使得left + right的和更大一些，从而更接近twoSumTarget。

【一点心得】

　　在O(N^2）的算法中，考虑加入O(NlgN) 的排序操作。特别是遇到需要去除重复的时候，利用排序 + Two Pointers 来达到 HashSet的效果。

 1 public class Solution {
 2     public List<List<Integer>> threeSum(int[] nums) {
 3         List<List<Integer>> result = new ArrayList<List<Integer>>();
 4         int len = nums.length;
 5         if (len < 3) {
 6             return result;
 7         }
 8         
 9         Arrays.sort(nums);
10         
11         // for all number that can be the 1st number of triplet
12         for (int i = 0; i < len - 1; i++) {
13             int firstNumber = nums[i];
14             
15             // skip all duplicated first number
16             if (i == 0 || firstNumber != nums[i - 1]) {
17                 
18                 int leftIndex  = i + 1;
19                 int rightIndex = len - 1;
20                 int twoSumTarget = 0 - firstNumber;
21                 
22                 // try to find two numbers that sum up to twoSumTarget
23                 while (leftIndex < rightIndex) {
24                     int twoSum = nums[leftIndex] + nums[rightIndex];
25                     if (twoSum == twoSumTarget) {
26                         // one valid triplet found!!
27                         result.add(Arrays.asList(firstNumber, nums[leftIndex], nums[rightIndex]));
28                         // skip duplicated nums[leftIndex]
29                         while (leftIndex < rightIndex && nums[leftIndex] == nums[leftIndex + 1]) {
30                             leftIndex++;
31                         }
32                         // skip duplicated nums[rightIndex]
33                         while (leftIndex < rightIndex && nums[rightIndex] == nums[rightIndex - 1]) {
34                             rightIndex--;
35                         }
36                         // move to next non-duplicates
37                         leftIndex++;
38                         rightIndex--;
39                     } else if (twoSum < twoSumTarget) {
40                         // move left towards right to 
41                         // make twoSum larger to get closer to twoSumTarget
42                         leftIndex++;
43                     } else {
44                         rightIndex--;
45                     }
46                 }
47                 
48             }
49         }
50         
51         return result;
52     }
53 }