如何稳定地做个渣渣1

如前所述，我是个渣渣，所以我肯定是不会写代码的，只会抄。所以下面所述代码都是抄的，相应链接都已标出。

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道题已经是极限了，今天就到此为止。

如果大神们荣幸认真看了并且发现任何错误，一定要喷我，不用留面子。