如前所述，我是个渣渣，所以我肯定是不会写代码的，只会抄。所以下面所述代码都是抄的，相应链接都已标出。
LC1. 2 Sum
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
Easy题，但我也不会，所以直接看答案。链接：LeetCode题解，151道题完整版
代码:
class Solution {
public:
vector<int> twoSum(vector<int> &nums, int target)
{
unordered_map<int, int> mapping;
vector<int> result;
for (int i = 0; i < nums.size(); i++)
{
mapping[nums[i]] = i;
}
for (int i = 0; i < nums.size(); i++)
{
const int gap = target - nums[i];
if (mapping.find(gap) != mapping.end() && mapping[gap] > i)
{
result.push_back(i + 1);
result.push_back(mapping[gap] + 1); break;
}
}
return result;
}
};
思路很简单，用hash_map来存每一个元素及其对应的索引，然后查找每一个元素对应的半个值，找到之后返回索引
然后我在假装看懂了之后就去提交，结果发现一个小问题：
这是旧答案，新题目不要求返回的索引必须不为0，因此 result.push_back(i + 1); result.push_back(mapping[gap] + 1);这两行代码中push_back的索引不需要+1秒。
在另一个网站看到了一种解法，虽然同样是用hash_map，但对边界的判断不同。基本一样就不细说了，就是更麻烦一点，所以时间差一些。链接
15. 3 Sum
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]
]
给定一组数，从里面找出相加等于0的三个数的全部组合。稍微有点难，median。首先一定是要排序的，直接sort快排，排好之后从第二个元素和最后一个元素依次向中间夹逼，是的，夹逼。
Solution:
class Solution {
public:
vector<vector<int> > threeSum(vector<int>& nums) {
vector<vector<int> > result;
if(nums.size() < 3)
return result;
sort(nums.begin(), nums.end());
const int target = 0;
auto last = nums.end();
for(auto i = nums.begin(); i < last - 2; ++i)
{
auto j = i + 1;
if(i > nums.begin() && *i == *(i - 1))
continue;
auto k = last - 1;
while(j < k)
{
if(*i + *j + *k < target)
{
++j;
while(*j == *(j-1) && j<k)
++j;
}
else if(*i + *j + *k > target)
{
--k;
while(*k == *(k+1) && j<k)
--k;
}
else
{
result.push_back({*i, *j, *k});
++j;
--k;
while(*j == *(j-1) && *k == *(k+1) && j<k)
++j;
}
}
}
return result;
}
};
这道题没什么坑。
小细节在于始终要保持指针j<k，所以每一个判断里都要进行判断。剩下的就是普通的遍历了，连我都能看懂，应该是很简单了吧。
3 Sum Closest
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
延续上一题，给定一组数，求三个数的和与目标值最接近的组合。有且仅有一组解。这就好办多了。同样是先排序后夹逼。
一开始看这个解法有一个困惑，为什么gap = abs(sum - target)并且如果sum < target，b就继续向后移动呢？因为如果sum > target，也就没有继续找更大的值得必要了，所以当前值就是closest的。
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target)
{
int result;
int min_gap = INT_MAX;
sort(nums.begin(), nums.end());
for(auto a = nums.begin(); a != prev(nums.end(), 2); ++a)
{
auto b = next(a);
auto c = prev(nums.end());
while(b<c)
{
const int sum = *a + *b + *c;
const int gap = abs(sum - target);
if(gap < min_gap)
{
min_gap = gap;
result = sum;
}
if(sum < target)
++b;
else
--c;
}
}
return result;
}
};
128. Longest Consecutive Sequence
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.
Your algorithm should run in O(n) complexity.
要求O(n)，所以肯定不能暴力膜，也不能先排序，所以还是用hash_map，保存每个元素是否被使用，“使用”的意思是该元素有与其连续的元素。以当前元素为中心，向左右遍历每一个元素。查找当前元素的连续元素，找到就把hash_map中的此元素置为true，表示已使用；未找到就继续找下一个元素的连续元素。（简直像他妈绕口令一样）
class Solution {
public:
int longestConsecutive(vector<int>& nums)
{
unordered_map<int, bool> used;
for(auto i:nums)
used[i] = false;
int longest = 0;
for(auto i:nums)
{
if(used[i] == true)
continue;
int length = 1;
used[i] = true;
for(int j = i + 1; used.find(j) != used.end(); ++j)
{
used[j] = true;
++length;
}
for(int j = i - 1; used.find(j) != used.end(); --j)
{
used[j] = true;
++length;
}
longest = max(length, longest);
}
return longest;
}
};
有一个小细节很巧妙（起码我觉得很巧妙），longest = max(length, longest);这句保证了输入为空时可以返回为0的longest，不为空时返回所有查找中最长的一次值。
好了，第一篇就到此为止。由于实在太渣了，3道题已经是极限了，今天就到此为止。
如果大神们荣幸认真看了并且发现任何错误，一定要喷我，不用留面子。
网友评论