分享我的Lintcode题解，目前进度244/248

2 Sum
题意：给定一个未排序的数组，请找出是否存在a{i} + a{j} = target。返回i和j，要求i < j。
解法1：hashing显然是方便又高效。
代码1：

1. // The O(n) solution by hashing
   
2. #include <unordered_map>
   
3. using namespace std;
   
4. 
   
5. class Solution {
   
6. public:
   
7.     /*
   
8.      * @param numbers : An array of Integer
   
9.      * @param target : target = numbers[index1] + numbers[index2]
   
10.      * @return : [index1+1, index2+1] (index1 < index2)
    
11.      */
    
12.     vector<int> twoSum(vector<int> &nums, int target) {
    
13.         vector<int> &a = nums;
    
14.         vector<int> ans;
    
15.         int n = a.size();
    
16.         unordered_map<int, int> um;
    
17.         unordered_map<int, int>::iterator it;
    
18.         
    
19.         int i;
    
20.         for (i = 0; i < n; ++i) {
    
21.             it = um.find(target - a[i]);
    
22.             if (it != um.end()) {
    
23.                 ans.push_back(it->second + 1);
    
24.                 ans.push_back(i + 1);
    
25.                 break;
    
26.             }
    
27.             um[a[i]] = i;
    
28.         }
    
29.         return ans;
    
30.     }
    
31. };

复制代码

复杂度1：时间O(N)，空间O(N)。

解法2：在有序数组中求two sum可以用O(N)时间，O(1)空间。但是这题需要先排序（于是会改变各元素的位置），然后还要返回元素在原数组中的位置。所以我不知道如何做到O(1)空间？
代码2：

1. // O(n * log(n)) solution with O(n) space
   
2. #include <algorithm>
   
3. using namespace std;
   
4. 
   
5. struct Term {
   
6.     int val;
   
7.     int i;
   
8. };
   
9. 
   
10. bool comp(const Term &x, const Term &y)
    
11. {
    
12.         return x.val < y.val;
    
13. }
    
14. 
    
15. class Solution {
    
16. public:
    
17.     /*
    
18.      * @param numbers : An array of Integer
    
19.      * @param target : target = numbers[index1] + numbers[index2]
    
20.      * @return : [index1+1, index2+1] (index1 < index2)
    
21.      */
    
22.     vector<int> twoSum(vector<int> &nums, int target) {
    
23.         vector<int> &a = nums;
    
24.         int n = a.size();
    
25.         vector<Term> v(n);
    
26.         
    
27.         int i, j;
    
28.         for (i = 0; i < n; ++i) {
    
29.             v[i].val = a[i];
    
30.             v[i].i = i + 1;
    
31.         }
    
32.         sort(v.begin(), v.end(), comp);
    
33.         
    
34.         vector<int> ans(2);
    
35.         i = 0;
    
36.         j = n - 1;
    
37.         while (i < j) {
    
38.             if (v[i].val + v[j].val < target) {
    
39.                 ++i;
    
40.             } else if (v[i].val + v[j].val > target) {
    
41.                 --j;
    
42.             } else {
    
43.                 ans[0] = v[i].i;
    
44.                 ans[1] = v[j].i;
    
45.                 if (ans[0] > ans[1]) {
    
46.                     swap(ans[0], ans[1]);
    
47.                 }
    
48.                 break;
    
49.             }
    
50.         }
    
51.         return ans;
    
52.     }
    
53. };

复制代码

复杂度2：时间O(N * log(N))，空间O(N)。

3 Sum
题意：给定一个未排序的数组，求所有加起来等于target的a{i} + a{j} + a{k}组合。要求不能重复，而且三元组必须是升序的。
解法1：首先排序，然后逐个元素求two sum。对于判重，我用的是比较偷懒的算签名查哈希的方法。实际上你用任何效率不算低的签名算法都可以，只要别发生碰撞就行了。
代码1：

1. #include <algorithm>
   
2. #include <string>
   
3. #include <unordered_set>
   
4. using namespace std;
   
5. 
   
6. class Solution {
   
7. public:   
   
8.     /**
   
9.      * @param numbers : Give an array numbers of n integer
   
10.      * @return : Find all unique triplets in the array which gives the sum of zero.
    
11.      */
    
12.     vector<vector<int> > threeSum(vector<int> &nums) {
    
13.         vector<int> &a = nums;
    
14.         vector<int> v(3);
    
15.         int n = a.size();
    
16.         
    
17.         ans.clear();
    
18.         int i, j, k;
    
19.         sort(a.begin(), a.end());
    
20.         for (i = 0; i < n - 2; ++i) {
    
21.             j = i + 1;
    
22.             k = n - 1;
    
23.             while (j < k) {
    
24.                 if (a[i] + a[j] + a[k] < 0) {
    
25.                     ++j;
    
26.                 } else if (a[i] + a[j] + a[k] > 0) {
    
27.                     --k;
    
28.                 } else {
    
29.                     string s = calcSign(a[i], a[j], a[k]);
    
30.                     if (us.find(s) == us.end()) {
    
31.                         v[0] = a[i];
    
32.                         v[1] = a[j];
    
33.                         v[2] = a[k];
    
34.                         ans.push_back(v);
    
35.                         us.insert(s);
    
36.                     }
    
37.                     ++j;
    
38.                 }
    
39.             }
    
40.         }
    
41.         us.clear();
    
42.         return ans;
    
43.     }
    
44. private:
    
45.     unordered_set<string> us;
    
46.     vector<vector<int> > ans;
    
47.    
    
48.     string calcSign(int a, int b, int c) {
    
49.         return to_string(a) + to_string(b) + to_string(c);
    
50.     }
    
51. };

复制代码

复杂度1：时间O(N ^ 2)，空间理论上是O(N ^ 3)，因为解的个数是O(N ^ 3)规模的。

解法2：再来个不用哈希的，刚写好。
代码2：

1. // O(1) space
   
2. #include <algorithm>
   
3. using namespace std;
   
4. 
   
5. class Solution {
   
6. public:   
   
7.     /**
   
8.      * @param numbers : Give an array numbers of n integer
   
9.      * @return : Find all unique triplets in the array which gives the sum of zero.
   
10.      */
    
11.     vector<vector<int> > threeSum(vector<int> &nums) {
    
12.         vector<int> &a = nums;
    
13.         vector<int> v(3);
    
14.         int n = a.size();
    
15.         
    
16.         ans.clear();
    
17.         int i, j, k;
    
18.         sort(a.begin(), a.end());
    
19.         int val;
    
20.         i = 0;
    
21.         while (i < n) {
    
22.             j = i + 1;
    
23.             k = n - 1;
    
24.             while (j < k) {
    
25.                 if (a[i] + a[j] + a[k] < 0) {
    
26.                     ++j;
    
27.                 } else if (a[i] + a[j] + a[k] > 0) {
    
28.                     --k;
    
29.                 } else {
    
30.                     v[0] = a[i];
    
31.                     v[1] = a[j];
    
32.                     v[2] = a[k];
    
33.                     ans.push_back(v);
    
34.                     val = j;
    
35.                     j = nextPos(a, k, j);
    
36.                 }
    
37.             }
    
38.             i = nextPos(a, n, i);
    
39.         }
    
40.         return ans;
    
41.     }
    
42. private:
    
43.     vector<vector<int> > ans;
    
44.    
    
45.     int nextPos(vector<int> &a, int n, int i) {
    
46.         int val = a[i];
    
47.         while (i < n && a[i] == val) {
    
48.             ++i;
    
49.         }
    
50.         return i;
    
51.     }
    
52. };

复制代码

复杂度2：时间O(N)，空间O(1)。其实空间也不算严格O(1)，因为我不会刻意为了追求O(1)空间而把本来可以复用的代码重复贴几遍。

4 Sum
题意：给定一个未排序数组，求其中加起来等于target的组合a + b + c + d。
解法1：两个维度用遍历解决，另两个维度使用two sum的解法。查重依然是偷懒的签名+哈希。话说我要是用位运算配合加减法来算签名，应该速度会快得多吧。
代码1：

1. #include <algorithm>
   
2. #include <string>
   
3. #include <unordered_set>
   
4. using namespace std;
   
5. 
   
6. class Solution {
   
7. public:
   
8.     /**
   
9.      * @param numbers: Give an array numbersbers of n integer
   
10.      * @param target: you need to find four elements that's sum of target
    
11.      * @return: Find all unique quadruplets in the array which gives the sum of
    
12.      *          zero.
    
13.      */
    
14.     vector<vector<int> > fourSum(vector<int> nums, int target) {
    
15.         ans.clear();
    
16.         vector<int> &a = nums;
    
17.         vector<int> v(4);
    
18.         int n = nums.size();
    
19.         int i1, i2, i3, i4;
    
20.         
    
21.         sort(a.begin(), a.end());
    
22.         for (i1 = 0; i1 < n - 3; ++i1) {
    
23.             for (i4 = i1 + 3; i4 < n; ++i4) {
    
24.                 i2 = i1 + 1;
    
25.                 i3 = i4 - 1;
    
26.                 while (i2 < i3) {
    
27.                     if (a[i1] + a[i2] + a[i3] + a[i4] < target) {
    
28.                         ++i2;
    
29.                     } else if (a[i1] + a[i2] + a[i3] + a[i4] > target) {
    
30.                         --i3;
    
31.                     } else {
    
32.                         v[0] = a[i1];
    
33.                         v[1] = a[i2];
    
34.                         v[2] = a[i3];
    
35.                         v[3] = a[i4];
    
36.                         string s = calcSign(v);
    
37.                         if (us.find(s) == us.end()) {
    
38.                             ans.push_back(v);
    
39.                             us.insert(s);
    
40.                         }
    
41.                         ++i2;
    
42.                     }
    
43.                 }
    
44.             }
    
45.         }
    
46.         us.clear();
    
47.         return ans;
    
48.     }
    
49. private:
    
50.     unordered_set<string> us;
    
51.     vector<vector<int> > ans;
    
52.    
    
53.     string calcSign(vector<int> &v) {
    
54.         int n = v.size();
    
55.         string s = "";
    
56.         int i;
    
57.         for (i = 0; i < n; ++i) {
    
58.             s += to_string(v[i]);
    
59.         }
    
60.         return s;
    
61.     }
    
62. };

复制代码

复杂度1：时间O(N ^ 3)，空间O(N ^ 4)。

解法2：依然是用跳过相等元素的方法来去重。
代码2：

1. // Without hashing
   
2. #include <algorithm>
   
3. using namespace std;
   
4. 
   
5. class Solution {
   
6. public:
   
7.     /**
   
8.      * @param numbers: Give an array numbersbers of n integer
   
9.      * @param target: you need to find four elements that's sum of target
   
10.      * @return: Find all unique quadruplets in the array which gives the sum of
    
11.      *          zero.
    
12.      */
    
13.     vector<vector<int> > fourSum(vector<int> nums, int target) {
    
14.         ans.clear();
    
15.         vector<int> &a = nums;
    
16.         vector<int> v(4);
    
17.         int n = nums.size();
    
18.         int i1, i2, i3, i4;
    
19.         
    
20.         sort(a.begin(), a.end());
    
21.         i1 = 0;
    
22.         while(i1 < n) {
    
23.             i4 = n - 1;
    
24.             while (i4 > i1) {
    
25.                 i2 = i1 + 1;
    
26.                 i3 = i4 - 1;
    
27.                 while (i2 < i3) {
    
28.                     if (a[i1] + a[i2] + a[i3] + a[i4] < target) {
    
29.                         ++i2;
    
30.                     } else if (a[i1] + a[i2] + a[i3] + a[i4] > target) {
    
31.                         --i3;
    
32.                     } else {
    
33.                         v[0] = a[i1];
    
34.                         v[1] = a[i2];
    
35.                         v[2] = a[i3];
    
36.                         v[3] = a[i4];
    
37.                         ans.push_back(v);
    
38.                         i2 = nextPos(a, n, i2);
    
39.                     }
    
40.                 }
    
41.                 i4 = lastPos(a, i1, i4);
    
42.             }
    
43.             i1 = nextPos(a, n, i1);
    
44.         }
    
45.         return ans;
    
46.     }
    
47. private:
    
48.     vector<vector<int> > ans;
    
49.    
    
50.     int lastPos(vector<int> &a, int n, int i) {
    
51.         int val = a[i];
    
52.         while (i > n && a[i] == val) {
    
53.             --i;
    
54.         }
    
55.         return i;
    
56.     }
    
57.    
    
58.     int nextPos(vector<int> &a, int n, int i) {
    
59.         int val = a[i];
    
60.         while (i < n && a[i] == val) {
    
61.             ++i;
    
62.         }
    
63.         return i;
    
64.     }
    
65. };

复制代码

复杂度2：时间O(N ^ 3)，空间O(1)。

3 Sum Closest
题意：给定一个未排序的数组，找出加起来和target最接近的a + b + c。答案保证唯一。
解法：第一个维度用遍历的，后两个维度使用two sum的做法，不过这次要随时更新答案。如果找到等于target的，就可以直接退出了。
代码：

1. #include <algorithm>
   
2. using namespace std;
   
3. 
   
4. class Solution {
   
5. public:   
   
6.     /**
   
7.      * @param numbers: Give an array numbers of n integer
   
8.      * @param target: An integer
   
9.      * @return: return the sum of the three integers, the sum closest target.
   
10.      */
    
11.     int threeSumClosest(vector<int> nums, int target) {
    
12.         vector<int> &a = nums;
    
13.         int n = a.size();
    
14.         int i, j, k;
    
15.         int ans;
    
16.         
    
17.         sort(a.begin(), a.end());
    
18.         ans = a[0] + a[1] + a[2];
    
19.         int s;
    
20.         for (i = 0; i < n - 2; ++i) {
    
21.             j = i + 1;
    
22.             k = n - 1;
    
23.             while (j < k) {
    
24.                 s = a[i] + a[j] + a[k];
    
25.                 if (s < target) {
    
26.                     if (abs(s - target) < abs(ans - target)) {
    
27.                         ans = s;
    
28.                     }
    
29.                     ++j;
    
30.                 } else if (s > target) {
    
31.                     if (abs(s - target) < abs(ans - target)) {
    
32.                         ans = s;
    
33.                     }
    
34.                     --k;
    
35.                 } else {
    
36.                     return target;
    
37.                 }
    
38.             }
    
39.         }
    
40.         return ans;
    
41.     }
    
42. private:
    
43.     int abs(int x) {
    
44.         return x >= 0 ? x : -x;
    
45.     }
    
46. };

复制代码

复杂度：时间O(N ^ 2)，空间O(1)。

Search Insert Position
题意：在有序数组中插入一个元素，保证依然有序。求插入的位置。
解法1：二分
代码1：

1. class Solution {
   
2.     /**
   
3.      * param A : an integer sorted array
   
4.      * param target :  an integer to be inserted
   
5.      * return : an integer
   
6.      */
   
7. public:
   
8.     int searchInsert(vector<int> &A, int target) {
   
9.         int n = A.size();
   
10.         if (n == 0 || target > A[n - 1]) {
    
11.             return n;
    
12.         }
    
13.         if (target <= A[0]) {
    
14.             return 0;
    
15.         }
    
16.         int ll, rr, mm;
    
17.         
    
18.         ll = 0;
    
19.         rr = n - 1;
    
20.         while (rr - ll > 1) {
    
21.             mm = (ll + rr) / 2;
    
22.             if (A[mm] < target) {
    
23.                 ll = mm;
    
24.             } else {
    
25.                 rr = mm;
    
26.             }
    
27.         }
    
28.         return rr;
    
29.     }
    
30. };

复制代码

复杂度1：时间O(log(N))，空间O(1)。

解法2：lower_bound。
代码2：

1. #include <algorithm>
   
2. using namespace std;
   
3. 
   
4. class Solution {
   
5.     /**
   
6.      * param A : an integer sorted array
   
7.      * param target :  an integer to be inserted
   
8.      * return : an integer
   
9.      */
   
10. public:
    
11.     int searchInsert(vector<int> &A, int target) {
    
12.         return lower_bound(A.begin(), A.end(), target) - A.begin();
    
13.     }
    
14. };

复制代码

复杂度2：一样

Search for a Range
题意：给定一个有序数组和target，求数组中等于target的元素的起始位置。
解法：二分，用lower_bound和upper_bound。
代码：

1. class Solution {
   
2.     /**
   
3.      *@param A : an integer sorted array
   
4.      *@param target :  an integer to be inserted
   
5.      *return : a list of length 2, [index1, index2]
   
6.      */
   
7. public:
   
8.     vector<int> searchRange(vector<int> &A, int target) {
   
9.         vector<int> ans(2);
   
10.         int n = A.size();
    
11.         if (n == 0) {
    
12.             ans[0] = ans[1] = -1;
    
13.             return ans;
    
14.         }
    
15.         ans[0] = lower_bound(A.begin(), A.end(), target) - A.begin();
    
16.         if (A[ans[0]] != target) {
    
17.             ans[0] = ans[1] = -1;
    
18.             return ans;
    
19.         }
    
20.         ans[1] = upper_bound(A.begin(), A.end(), target) - A.begin() - 1;
    
21.         return ans;
    
22.     }
    
23. };

复制代码

复杂度：时间O(log(N))，空间O(1)。

Search in Rotated Sorted Array
题意：在一个旋转过的有序数组中查找一个值，不含重复元素。
解法1：先找出旋转的位置，然后再二分查找。
代码1：

1. class Solution {
   
2.     /**
   
3.      * param A : an integer ratated sorted array
   
4.      * param target :  an integer to be searched
   
5.      * return : an integer
   
6.      */
   
7. public:
   
8.     int search(vector<int> &A, int target) {
   
9.         int n = A.size();
   
10.         if (n == 0) {
    
11.             return -1;
    
12.         }
    
13.         
    
14.         int ll, rr, mm;
    
15.         ll = 0;
    
16.         rr = n - 1;
    
17.         int k = findRotatePos(A);
    
18.         while (ll <= rr) {
    
19.             mm = (ll + rr) / 2;
    
20.             if (target < A[(mm + k) % n]) {
    
21.                 rr = mm - 1;
    
22.             } else if (target > A[(mm + k) % n]) {
    
23.                 ll = mm + 1;
    
24.             } else {
    
25.                 return (mm + k) % n;
    
26.             }
    
27.         }
    
28.         return -1;
    
29.     }
    
30. private:
    
31.     int findRotatePos(vector<int> &A) {
    
32.         int ll, rr, mm;
    
33.         int n = A.size();
    
34.         
    
35.         if (n <= 1) {
    
36.             return 0;
    
37.         }
    
38.         
    
39.         ll = 0;
    
40.         rr = n - 1;
    
41.         while (rr - ll > 1) {
    
42.             if (A[ll] < A[rr]) {
    
43.                 break;
    
44.             }
    
45.             if (A[ll] == A[rr]) {
    
46.                 --rr;
    
47.                 continue;
    
48.             }
    
49.             mm = (ll + rr) / 2;
    
50.             if (A[mm] >= A[ll]) {
    
51.                 ll = mm;
    
52.             } else {
    
53.                 rr = mm;
    
54.             }
    
55.         }
    
56.         return A[ll] < A[rr] ? ll : rr;
    
57.     }
    
58. };

复制代码

复杂度1：时间O(log(N))，空间O(1)。

解法2：其实可以直接二分，不用求出偏移量。这个代码更简洁些。
代码2：

1. class Solution {
   
2.     /**
   
3.      * param A : an integer ratated sorted array
   
4.      * param target :  an integer to be searched
   
5.      * return : an integer
   
6.      */
   
7. public:
   
8.     int search(vector<int> &A, int target) {
   
9.         int n = A.size();
   
10.         int ll, rr, mm;
    
11.         
    
12.         ll = 0;
    
13.         rr = n - 1;
    
14.         while (ll <= rr) {
    
15.             mm = ll + (rr - ll) / 2;
    
16.             if (A[mm] == target) {
    
17.                 return mm;
    
18.             }
    
19.             if (A[ll] < A[mm]) {
    
20.                 if (target >= A[ll] && target < A[mm]) {
    
21.                     rr = mm - 1;
    
22.                 } else {
    
23.                     ll = mm + 1;
    
24.                 }
    
25.             } else if (A[mm] < A[rr]) {
    
26.                 if (target > A[mm] && target <= A[rr]) {
    
27.                     ll = mm + 1;
    
28.                 } else {
    
29.                     rr = mm - 1;
    
30.                 }
    
31.             } else {
    
32.                 // In case there're duplicates
    
33.                 ++ll;
    
34.             }
    
35.         }
    
36.         return -1;
    
37.     }
    
38. };

复制代码

复杂度2：一样。

Search in Rotated Sorted Array II
题意：在一个旋转过的有序数组中，查找一个值是否存在，可以有重复元素。
解法1：找出旋转的位置，然后二分搜索。
代码1：

1. class Solution {
   
2.     /**
   
3.      * param A : an integer ratated sorted array and duplicates are allowed
   
4.      * param target :  an integer to be search
   
5.      * return : a boolean
   
6.      */
   
7. public:
   
8.     bool search(vector<int> &A, int target) {
   
9.         int n = A.size();
   
10.         if (n == 0) {
    
11.             return false;
    
12.         }
    
13.         
    
14.         int ll, rr, mm;
    
15.         ll = 0;
    
16.         rr = n - 1;
    
17.         int k = findRotatePos(A);
    
18.         while (ll <= rr) {
    
19.             mm = (ll + rr) / 2;
    
20.             if (target < A[(mm + k) % n]) {
    
21.                 rr = mm - 1;
    
22.             } else if (target > A[(mm + k) % n]) {
    
23.                 ll = mm + 1;
    
24.             } else {
    
25.                 return true;
    
26.             }
    
27.         }
    
28.         return false;
    
29.     }
    
30. private:
    
31.     int findRotatePos(vector<int> &A) {
    
32.         int ll, rr, mm;
    
33.         int n = A.size();
    
34.         
    
35.         if (n <= 1) {
    
36.             return 0;
    
37.         }
    
38.         
    
39.         ll = 0;
    
40.         rr = n - 1;
    
41.         while (rr - ll > 1) {
    
42.             if (A[ll] < A[rr]) {
    
43.                 break;
    
44.             }
    
45.             if (A[ll] == A[rr]) {
    
46.                 --rr;
    
47.                 continue;
    
48.             }
    
49.             mm = (ll + rr) / 2;
    
50.             if (A[mm] >= A[ll]) {
    
51.                 ll = mm;
    
52.             } else {
    
53.                 rr = mm;
    
54.             }
    
55.         }
    
56.         return A[ll] < A[rr] ? ll : rr;
    
57.     }
    
58. };

复制代码

复杂度1：时间O(log(N))，空间O(1)。

解法2：直接二分搜索，代码写得不太简洁，欠缺美感。
代码2：

1. class Solution {
   
2.     /**
   
3.      * param A : an integer ratated sorted array
   
4.      * param target :  an integer to be searched
   
5.      * return : an integer
   
6.      */
   
7. public:
   
8.     bool search(vector<int> &A, int target) {
   
9.         int n = A.size();
   
10.         int ll, rr, mm;
    
11.         
    
12.         ll = 0;
    
13.         rr = n - 1;
    
14.         while (ll <= rr) {
    
15.             if (A[ll] == target) {
    
16.                 return true;
    
17.             }
    
18.             if (A[ll] == A[rr]) {
    
19.                 ++ll;
    
20.                 continue;
    
21.             }
    
22.             mm = ll + (rr - ll) / 2;
    
23.             if (A[mm] == target) {
    
24.                 return true;
    
25.             }
    
26.             if (A[ll] < A[mm]) {
    
27.                 if (target >= A[ll] && target < A[mm]) {
    
28.                     rr = mm - 1;
    
29.                 } else {
    
30.                     ll = mm + 1;
    
31.                 }
    
32.             } else if (A[mm] < A[rr]) {
    
33.                 if (target > A[mm] && target <= A[rr]) {
    
34.                     ll = mm + 1;
    
35.                 } else {
    
36.                     rr = mm - 1;
    
37.                 }
    
38.             } else {
    
39.                 // In case there're duplicates
    
40.                 ++ll;
    
41.             }
    
42.         }
    
43.         return false;
    
44.     }
    
45. };

复制代码

复杂度2：一样。

没想到刷的时候感觉挺流畅的，现在回过头看自己刚写的代码，就是各种漏洞，各种不全面。

之后又翻了翻自己一年前刷leetcode时写的代码，简直是烂。。。

然后又翻了翻自己几年前ZOJ、POJ刷的题，那都不能叫代码了~

于是从好的一面说：我真是进步了。
从坏的一面说：我是有多菜，进步到现在才这样。。。
所以我明白了leetcode为什么要多刷两遍了。因为第一遍的时候，还不懂这东西该怎么玩，可能AC了就完事，光刷成就感了，没有以全面思考为目的。

今天先到这儿，累了~