Optimization solution 0015

halfrost · halfrost · commit 3e2d511c6b73 · 2021-01-02T01:04:43.000+08:00
diff --git a/leetcode/0015.3Sum/15. 3Sum.go b/leetcode/0015.3Sum/15. 3Sum.go
@@ -4,7 +4,44 @@ import (
 	"sort"
 )
 
+// 解法一 最优解，双指针 + 排序
 func threeSum(nums []int) [][]int {
+	sort.Ints(nums)
+	result, start, end, index, addNum, length := make([][]int, 0), 0, 0, 0, 0, len(nums)
+	if length > 0 && (nums[0] > 0 || nums[length-1] < 0) {
+		return result
+	}
+	for index = 1; index < length-1; index++ {
+		start, end = 0, length-1
+		if index > 1 && nums[index] == nums[index-1] {
+			start = index - 1
+		}
+		for start < index && end > index {
+			if start > 0 && nums[start] == nums[start-1] {
+				start++
+				continue
+			}
+			if end < length-1 && nums[end] == nums[end+1] {
+				end--
+				continue
+			}
+			addNum = nums[start] + nums[end] + nums[index]
+			if addNum == 0 {
+				result = append(result, []int{nums[start], nums[index], nums[end]})
+				start++
+				end--
+			} else if addNum > 0 {
+				end--
+			} else {
+				start++
+			}
+		}
+	}
+	return result
+}
+
+// 解法二
+func threeSum1(nums []int) [][]int {
 	res := [][]int{}
 	counter := map[int]int{}
 	for _, value := range nums {
diff --git a/website/content/ChapterFour/0015.3Sum.md b/website/content/ChapterFour/0015.3Sum.md
@@ -42,7 +42,44 @@ import (
 	"sort"
 )
 
+// 解法一 最优解，双指针 + 排序
 func threeSum(nums []int) [][]int {
+	sort.Ints(nums)
+	result, start, end, index, addNum, length := make([][]int, 0), 0, 0, 0, 0, len(nums)
+	if length > 0 && (nums[0] > 0 || nums[length-1] < 0) {
+		return result
+	}
+	for index = 1; index < length-1; index++ {
+		start, end = 0, length-1
+		if index > 1 && nums[index] == nums[index-1] {
+			start = index - 1
+		}
+		for start < index && end > index {
+			if start > 0 && nums[start] == nums[start-1] {
+				start++
+				continue
+			}
+			if end < length-1 && nums[end] == nums[end+1] {
+				end--
+				continue
+			}
+			addNum = nums[start] + nums[end] + nums[index]
+			if addNum == 0 {
+				result = append(result, []int{nums[start], nums[index], nums[end]})
+				start++
+				end--
+			} else if addNum > 0 {
+				end--
+			} else {
+				start++
+			}
+		}
+	}
+	return result
+}
+
+// 解法二
+func threeSum1(nums []int) [][]int {
 	res := [][]int{}
 	counter := map[int]int{}
 	for _, value := range nums {
@@ -76,6 +113,7 @@ func threeSum(nums []int) [][]int {
 }
 
 
+
 ```
 
 
