Feng2012
diff --git a/‎src/0287.Find-the-Duplicate-Number/README.md
Lines changed: 74 additions & 0 deletions b/‎src/0287.Find-the-Duplicate-Number/README.md
Lines changed: 74 additions & 0 deletions
diff --git a/‎src/0287.Find-the-Duplicate-Number/Solution.go
Lines changed: 63 additions & 0 deletions b/‎src/0287.Find-the-Duplicate-Number/Solution.go
Lines changed: 63 additions & 0 deletions
diff --git a/‎src/0287.Find-the-Duplicate-Number/Solution_test.go
Lines changed: 40 additions & 0 deletions b/‎src/0287.Find-the-Duplicate-Number/Solution_test.go
Lines changed: 40 additions & 0 deletions
@@ -0,0 +1,74 @@
+# [# [1. Add Sum][title]
+
+## Description
+
+给定一个数组 nums 包含 n + 1 个整数，每个整数在 1 到 n 之间，包括 1 和 n。现在假设数组中存在一个重复的数字，找到该重复的数字。
+
+注意
+    不能修改数组元素，假设数组是只读的。
+    仅可以使用常数即O(1)O(1)的额外空间。
+    时间复杂度需要低于O(n2)O(n2)。
+    数组中仅有一个重复数字，但它可能重复超过1次。
+
+**Example 1:**
+
+```
+Example 1:
+
+Input: [1,3,4,2,2]
+Output: 2
+Example 2:
+
+Input: [3,1,3,4,2]
+Output: 3
+```
+
+**Tags:** Math, String
+
+## 题意
+> 这道题目主要应用了抽屉原理和分治的思想。
+  
+  抽屉原理：n+1 个苹果放在 n 个抽屉里，那么至少有一个抽屉中会放两个苹果。
+  
+  用在这个题目中就是，一共有 n+1 个数，每个数的取值范围是1到n，所以至少会有一个数出现两次。
+  
+  然后我们采用分治的思想，将每个数的取值的区间[1, n]划分成[1, n/2]和[n/2+1, n]两个子区间，然后分别统计两个区间中数的个数。
+  注意这里的区间是指 数的取值范围，而不是 数组下标。
+  
+  划分之后，左右两个区间里一定至少存在一个区间，区间中数的个数大于区间长度。
+  这个可以用反证法来说明：如果两个区间中数的个数都小于等于区间长度，那么整个区间中数的个数就小于等于n，和有n+1个数矛盾。
+  
+  因此我们可以把问题划归到左右两个子区间中的一个，而且由于区间中数的个数大于区间长度，根据抽屉原理，在这个子区间中一定存在某个数出现了两次。
+  
+  依次类推，每次我们可以把区间长度缩小一半，直到区间长度为1时，我们就找到了答案。
+  
+  作者：extrovert
+  链接：https://www.acwing.com/solution/LeetCode/content/2814/
+  来源：AcWing
+  著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
+
+- 复杂度分析
+时间复杂度：每次会将区间长度缩小一半，一共会缩小 O(logn) 次。每次统计两个子区间中的数时需要遍历整个数组，时间复杂度是 O(n)。所以总时间复杂度是 O(nlogn)。
+空间复杂度：代码中没有用到额外的数组，所以额外的空间复杂度是 O(1)。
+
+## 题解
+
+### 思路1
+> 。。。。
+
+```go
+
+```
+
+### 思路2
+> 思路2
+```go
+
+```
+
+## 结语
+
+如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：[awesome-golang-leetcode][me]
+
+[title]: https://leetcode.com/problems/two-sum/description/
+[me]: https://github.com/kylesliu/awesome-golang-leetcode
@@ -0,0 +1,63 @@
+package Solution
+
+import (
+	"math"
+	"sort"
+)
+
+//	二分
+func findDuplicate(nums []int) int {
+	left, right := 0, len(nums)-1
+	for left < right {
+		mid := (left + right) / 2
+		count := 0
+		for _, num := range nums {
+			if num <= mid {
+				count++
+			}
+		}
+		if count > mid {
+			right = mid
+		} else {
+			left = mid + 1
+		}
+	}
+	return left
+}
+
+//	排序
+func findDuplicate2(nums []int) int {
+	sort.Ints(nums)
+	for i := 1; i < len(nums); i++ {
+		if nums[i] == nums[i-1] {
+			return nums[i]
+		}
+	}
+	return 0
+}
+
+//	map
+func findDuplicate3(nums []int) int {
+	found := -1
+	m := make(map[int]int)
+	for _, v := range nums {
+		m[v]++
+		if m[v] > 1 {
+			found = v
+			break
+		}
+	}
+	return found
+}
+
+//	排序
+func findDuplicate4(nums []int) int {
+	for i := range nums {
+		tmp := int(math.Abs(float64(nums[i])))
+		if nums[tmp-1] < 0 {
+			return int(math.Abs(float64(nums[i])))
+		}
+		nums[tmp-1] = -nums[tmp-1]
+	}
+	return -1
+}
@@ -0,0 +1,40 @@
+package Solution
+
+import (
+	"reflect"
+	"strconv"
+	"testing"
+)
+
+func TestSolution(t *testing.T) {
+	//	测试用例
+	cases := []struct {
+		name   string
+		inputs []int
+		expect int
+	}{
+		{"TestCase", []int{1, 3, 4, 2, 2}, 2},
+		{"TestCase", []int{3, 1, 3, 4, 2}, 3},
+	}
+
+	//	开始测试
+	for i, c := range cases {
+		t.Run(c.name+" "+strconv.Itoa(i), func(t *testing.T) {
+			got := findDuplicate(c.inputs)
+			if !reflect.DeepEqual(got, c.expect) {
+				t.Fatalf("expected: %v, but got: %v, with inputs: %v",
+					c.expect, got, c.inputs)
+			}
+		})
+	}
+}
+
+//	压力测试
+func BenchmarkSolution(b *testing.B) {
+
+}
+
+//	使用案列
+func ExampleSolution() {
+
+}