feat: add 015

Blankj · Blankj · commit 57472974afd7 · 2017-10-14T23:37:09.000+08:00
diff --git a/README.md b/README.md
@@ -60,6 +60,7 @@
 |2|[Add Two Numbers][002]|Linked List, Math|
 |3|[Longest Substring Without Repeating Characters][003]|Hash Table, Two Pointers, String|
 |8|[String to Integer (atoi)][008]|Math, String|
+|15|[3Sum][015]|Array, Two Pointers|
 |19|[Remove Nth Node From End of List][019]|Linked List, Two Pointers|
 |554|[Brick Wall][554]|Hash Table|
 
@@ -115,6 +116,7 @@
 [002]: https://github.com/Blankj/awesome-java-leetcode/blob/master/note/002/README.md
 [003]: https://github.com/Blankj/awesome-java-leetcode/blob/master/note/003/README.md
 [008]: https://github.com/Blankj/awesome-java-leetcode/blob/master/note/008/README.md
+[015]: https://github.com/Blankj/awesome-java-leetcode/blob/master/note/015/README.md
 [019]: https://github.com/Blankj/awesome-java-leetcode/blob/master/note/019/README.md
 [554]: https://github.com/Blankj/awesome-java-leetcode/blob/master/note/554/README.md
 
diff --git a/note/010/README.md b/note/010/README.md
@@ -30,6 +30,38 @@ isMatch("aab", "c*a*b") → true
 
 题意是
 
+
+``` java
+class Solution {
+    public boolean isMatch(String s, String p) {
+        if (p.length() == 0) return s.length() == 0;
+        if (p.length() == 1) {
+            if (s.length() < 1) return false;
+            if (p.charAt(0) != s.charAt(0) && p.charAt(0) != '.') return false;
+            return true;
+        }
+        if (p.charAt(1) != '*') {
+            if (s.length() < 1) return false;
+            if (p.charAt(0) != s.charAt(0) && p.charAt(0) != '.') return false;
+            return isMatch(s.substring(1), p.substring(1));
+        } else {
+            // match 0 preceding element
+            if (isMatch(s, p.substring(2))) return true;
+            int i = 0;
+            // match 1 or more preceding element
+            while (i < s.length() && (p.charAt(0) == s.charAt(i) || p.charAt(0) == '.')) {
+                if (isMatch(s.substring(i + 1), p.substring(2))) {
+                    return true;
+                }
+                ++i;
+                return false;
+            }
+        }
+    }
+}
+```
+
+
 ``` java
 class Solution {
     public boolean isMatch(String s, String p) {
diff --git a/note/015/README.md b/note/015/README.md
@@ -0,0 +1,59 @@
+# [3Sum][title]
+
+## Description
+
+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]
+]
+```
+
+**Tags:** Array, Two Pointers
+
+
+## 思路
+
+题意是让你从数组中找出所有三个和为0的元素构成的非重复序列，这样的话我们可以把数组先做下排序，然后遍历这个排序数组，用两个指针分别指向当前元素的下一个和数组尾部，判断三者和与0的大小来移动两个指针，其中细节操作就是注意去重。
+
+``` java
+class Solution {
+    public List<List<Integer>> threeSum(int[] nums) {
+        Arrays.sort(nums);
+        List<List<Integer>> list = new ArrayList<>();
+        int i = 0;
+        while (i < nums.length - 2) {
+            if (nums[i] > 0) break;
+            int left = i + 1, right = nums.length - 1;
+            while (left < right) {
+                int sum = nums[i] + nums[left] + nums[right];
+                if (sum == 0) {
+                    list.add(Arrays.asList(nums[i], nums[left++], nums[right--]));
+                    while (left < right && nums[left] == nums[left - 1]) ++left;
+                    while (left < right && nums[right] == nums[right + 1]) --right;
+                } else if (sum < 0) ++left;
+                else --right;
+            }
+            while (nums[i] == nums[++i] && i < nums.length - 2) ;
+        }
+        return list;
+    }
+}
+```
+
+
+## 结语
+
+如果你同我一样热爱数据结构、算法、LeetCode，可以关注我GitHub上的LeetCode题解：[awesome-java-leetcode][ajl]
+
+
+
+[title]: https://leetcode.com/problems/3sum
+[ajl]: https://github.com/Blankj/awesome-java-leetcode
diff --git a/src/com/blankj/medium/_015/Solution.java b/src/com/blankj/medium/_015/Solution.java
@@ -0,0 +1,41 @@
+package com.blankj.medium._015;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+
+/**
+ * <pre>
+ *     author: Blankj
+ *     blog  : http://blankj.com
+ *     time  : 2017/04/23
+ *     desc  :
+ * </pre>
+ */
+public class Solution {
+    public List<List<Integer>> threeSum(int[] nums) {
+        Arrays.sort(nums);
+        List<List<Integer>> list = new ArrayList<>();
+        int i = 0;
+        while (i < nums.length - 2) {
+            if (nums[i] > 0) break;
+            int left = i + 1, right = nums.length - 1;
+            while (left < right) {
+                int sum = nums[i] + nums[left] + nums[right];
+                if (sum == 0) {
+                    list.add(Arrays.asList(nums[i], nums[left++], nums[right--]));
+                    while (left < right && nums[left] == nums[left - 1]) ++left;
+                    while (left < right && nums[right] == nums[right + 1]) --right;
+                } else if (sum < 0) ++left;
+                else --right;
+            }
+            while (nums[i] == nums[++i] && i < nums.length - 2) ;
+        }
+        return list;
+    }
+
+    public static void main(String[] args) {
+        Solution solution = new Solution();
+        System.out.println(solution.threeSum(new int[]{-1, 0, 1, 2, -1, -4}));
+    }
+}
